การวิเคราะห์แบบ Amortized สำหรับตัวนับไบนารีใน C++

Amortized Analysis คืออะไร?

วิเคราะห์ค่าเฉลี่ยของค่าใช้จ่าย (cost) ต่อ operation ในลำดับการทำงาน ไม่ใช่ average-case analysis แต่เป็น worst-case guarantee สำหรับลำดับ operations

ปัญหา: Binary Counter Increment

k-bit binary counter เริ่มที่ 0 ทำการ increment n ครั้ง

0000 → 0001 → 0010 → 0011 → 0100 → 0101 → 0110 → 0111 → 1000 → ...


ค่าใช้จ่ายของแต่ละ Increment
ค่าใช้จ่าย = จำนวน bit ที่พลิก (flip)

0000 → 0001: flip 1 bit (LSB)
0001 → 0010: flip 2 bits (LSB 1→0, bitถัดไป 0→1)
0011 → 0100: flip 3 bits
0111 → 1000: flip 4 bits


Aggregate Analysis
รวม bit flips ทั้งหมดใน n operations:

Bit 0 (LSB): flip ทุกครั้ง → n ครั้ง
Bit 1: flip ทุก 2 ครั้ง → n/2 ครั้ง
Bit 2: flip ทุก 4 ครั้ง → n/4 ครั้ง
...
Bit k: flip ทุก 2ᵏ ครั้ง → n/2ᵏ ครั้ง

Total flips = n + n/2 + n/4 + ... + n/2ᵏ < n × Σ(1/2ⁱ) = n × 2 = 2n

Amortized Cost
Amortized cost per operation = Total cost / n = 2n / n = O(1)

ตัวอย่างโค้ด C++ จำลอง
#include <iostream>
#include <vector>
using namespace std;

void increment(vector<int>& bits) {
    int i = bits.size() - 1;
    while (i >= 0 && bits[i] == 1) {
        bits[i] = 0;
        i--;
    }
    if (i >= 0) bits[i] = 1;
}

int main() {
    int k = 8; // 8-bit counter
    vector<int> bits(k, 0);
    int totalFlips = 0;
    int n = 16; // ทำ 16 increments
    
    for (int op = 0; op < n; op++) {
        int flips = 0;
        int i = k - 1;
        while (i >= 0 && bits[i] == 1) {
            bits[i] = 0;
            i--; flips++;
        }
        if (i >= 0) { bits[i] = 1; flips++; }
        totalFlips += flips;
        
        cout << "Op " << op+1 << ": ";
        for (int b : bits) cout << b;
        cout << " (flips: " << flips << ")" << endl;
    }
    
    cout << "\nTotal flips: " << totalFlips 
         << ", Amortized: " << (double)totalFlips/n << endl;
    return 0;
}

ผลลัพธ์ (บางส่วน)
Op 1: 00000001 (flips: 1)
Op 2: 00000010 (flips: 2)
Op 3: 00000011 (flips: 1)
Op 4: 00000100 (flips: 3)
...
Op 16: 00010000 (flips: 5)

Total flips: 31, Amortized: 1.9375 ≈ 2 = O(1)

สรุป
แม้ operation บางครั้งใช้ค่าใช้จ่ายสูง (O(k)) แต่ averaged over sequence เป็น O(1) ต่อ operation นี่คือพลังของ Amortized Analysis