Phân tích摊销 (Amortized Analysis) cho bộ đếm nhị phân C++

Phân tích摊销 tính chi phí trung bình của chuỗi thao tác, khác với trung bình trường hợp (average-case) vì có thể bao gồm trường hợp xấu.

Bộ đếm nhị phân k-bit: mảng bit khởi tạo 0. Thao tác tăng (increment): tìm bit 0 đầu tiên từ phải, đổi thành 1, các bit 1 bên phải đổi thành 0.

Ví dụ 8-bit: 00000000 → 00000001 → 00000010 → 00000011 → 00000100...

Chi phí摊销

Tổng số lần flip bit trong n lần increment: n + n/2 + n/4 + ... < 2n. Chi phí摊销 = O(n) / n = O(1) mỗi lần increment.

Ví dụ minh họa

#include <iostream>
using namespace std;

int main() {
    int number[] = {1,0,0,1,0,1,1,1};
    int length = 8;
    int i = length - 1;
    while (number[i] == 1) {
        number[i] = 0;
        i--;
    }
    if (i >= 0) number[i] = 1;
    for (int i = 0; i < length; i++)
        cout << number[i] << " ";
}

Kết quả

1 0 0 1 1 0 0 0