Phân tích Amortized — trực quan
Ba module minh họa vì sao một thao tác đôi khi đắt nhưng amortized (trung bình trên chuỗi) vẫn O(1).
1. Dynamic array grow (×2)
Mỗi append rẻ (chi phí 1). Khi đầy, capacity nhân đôi và copy toàn bộ (đắt). Theo dõi tổng copy và amortized cost/op hội tụ về hằng số.
length / capacity
0 / 0
tổng copy
0
tổng chi phí
0
amortized / op
—
Tổng copy = 1+2+4+8+... < 2n (cấp số nhân) ⟹ amortized hội tụ về hằng số ~2–3 dù vài op lẻ tốn O(n).
2. Binary counter increment
Mỗi increment lật các bit 1 đuôi thành 0 (carry) rồi 1 bit 0 thành 1. Worst-case lật cả k bit, nhưng amortized = 2 flip.
giá trị
0
flip lần này
0
tổng flip
0
flip / increment
—
Tổng flip = n + n/2 + n/4 + ... < 2n. Mỗi increment amortized đúng 2 flip (potential Φ = số bit 1).
3. Credit visualizer (accounting method)
Mỗi append "tính tiền" amortized = 3: 1 trả chi phí thực, 2 lưu thành credit (xu vàng). Khi grow, credit bị tiêu để trả copy — và không bao giờ âm.
length / cap
0 / 0
credit ngân hàng
0
tổng amortized
0
tổng actual
0
Nhấn "Append" để bắt đầu.
Bất biến: tổng amortized (3/op) ≥ tổng actual ⟹ credit luôn ≥ 0. Đó là điều kiện để chặn amortized hợp lệ.