Amortized analysis — ArrayList.add() O(1) dù đôi khi tốn O(n)

TL;DR: Amortized O(1) nghĩa là trung bình trên dãy thao tác worst-case, mỗi thao tác tốn hằng số thời gian — dù từng lần riêng lẻ đôi khi đắt. ArrayList dùng mảng nội bộ tự mở rộng: mỗi lần đầy thì sao chép toàn bộ sang mảng mới lớn hơn (O(n)), nhưng sau đó có nhiều chỗ trống cho các lần add tiếp theo (O(1)). Tổng n lần add tốn dưới 2n phép tính → amortized O(1). Growth factor 1.5x được chọn thay vì 2x vì tổng các block cũ đủ để allocator tái sử dụng (cần factor nhỏ hơn golden ratio ≈ 1.618). Amortized không bảo vệ khi workload ép thao tác đắt liên tiếp — pre-allocate với capacity đã biết để tránh resize hoàn toàn.

Bạn benchmark một triệu lần thêm phần tử vào mảng động. Đa số lần chạy tốn khoảng 100ns. Nhưng có khoảng 20 lần nhảy vọt lên gần 10ms — gấp 100.000 lần. Sau khi nhìn vào profiler, bạn thấy đó là các thời điểm mảng nội bộ phải resize.

Vậy hàm add là O(1) hay O(n)?

Câu trả lời là amortized O(1) — nghĩa là trung bình trên toàn bộ dãy thao tác, mỗi lần add tốn hằng số thời gian, dù từng lần riêng lẻ đôi khi tốn O(n). Tài liệu ArrayList ghi rõ: "The add operation runs in amortized constant time."

Bài này giải thích amortized từ bản chất: vì sao 1.5x growth factor được chọn, 3 phương pháp phân tích cụ thể, và lúc nào amortized cứu bạn — lúc nào nó lừa bạn.

1. Analogy — Tem bưu điện

Hầu hết các ngày, bạn mua một con tem rẻ tiền để gửi thư — tốn 1.000 VND.

Nhưng thỉnh thoảng bạn đặt mua hộp 100 con tem cùng lúc — tốn 100.000 VND cho một giao dịch.

Giao dịch đó đắt hơn 100 lần so với mua lẻ. Nhưng nếu bạn nhìn lại 100 lần "dán tem" kế tiếp, chi phí trung bình mỗi lần vẫn là 1.000 VND — bởi vì hộp tem đó dùng cho cả 100 lần dán sau.

Amortized chính là cách nhìn đó: rải chi phí một lần đắt ra nhiều lần thao tác, tính trung bình.

2. Ba khái niệm — Amortized, Average, Worst-case

Đây là điểm hay bị nhầm nhất:

Worst-case per operation: chi phí của từng thao tác riêng lẻ trong tình huống xấu nhất. add() worst case là O(n) — khi xảy ra resize, phải sao chép n phần tử.

Average case: trung bình trên các input ngẫu nhiên theo một distribution giả định. Phụ thuộc vào bạn giả định input đến như thế nào — nếu assumption sai, average case vô nghĩa.

Amortized: trung bình trên một dãy thao tác worst-case liên tiếp — không phụ thuộc distribution ngẫu nhiên. Đây là đảm bảo mạnh hơn average: dù input có xấu thế nào, trung bình dãy vẫn hằng số.

Lưu ý: với bảng băm, tài liệu nói "amortized O(1)" — thực ra là average case với assumption hàm hash tốt (như bài 01 đã đề cập). Mảng động thực sự có amortized O(1) theo nghĩa chặt hơn.

3. Ba phương pháp phân tích amortized

3.1 Phương pháp tổng hợp — Đếm tổng rồi chia

Cách đơn giản nhất: tính tổng chi phí của n thao tác, chia cho n.

Áp dụng cho mảng động với grow factor 2x, bắt đầu từ capacity 1:

n lần add():
- add() lần 1: capacity = 1, không resize. Chi phí = 1.
- add() lần 2: resize từ 1 lên 2, sao chép 1 phần tử. Chi phí = 1 + 1 = 2.
- add() lần 3: resize từ 2 lên 4, sao chép 2 phần tử. Chi phí = 1 + 2 = 3.
- add() lần 5: resize từ 4 lên 8, sao chép 4 phần tử. Chi phí = 1 + 4 = 5.
- Hầu hết lần add(): không resize. Chi phí = 1.

Tổng chi phí sau n lần add():

• Chi phí sao chép (tổng cộng): 1 + 2 + 4 + 8 + ... + n/2 — chuỗi hình học bằng n - 1.
• Chi phí insert: n (mỗi lần add tốn 1).
• Tổng: n + (n - 1) < 2n.

Amortized cost mỗi op: 2n / n = 2 = O(1).

Phương pháp tổng hợp phù hợp khi tổng chi phí có dạng đơn giản để tính.

3.2 Phương pháp kế toán — Trả trước, rút sau

Mỗi thao tác được "tính phí" nhiều hơn chi phí thực — phần dư tích vào tài khoản. Khi thao tác đắt xảy ra, rút tài khoản để bù.

Với mảng động grow 2x: gán amortized cost = 3 cho mỗi add():

• 1 đơn vị để thực hiện insert.
• 1 đơn vị trả trước cho chi phí sao chép bản thân khi resize sau này.
• 1 đơn vị trả trước cho sao chép một phần tử cũ khi resize.

Tại sao 3 đơn vị là đủ?

Sau khi resize lên capacity = 2k (từ k):
- Có k phần tử cần sao chép.
- Các add() tiếp theo: k lần add trước khi resize tiếp.
- Mỗi lần add tích 2 đơn vị vào tài khoản -> k * 2 = 2k đơn vị.
- Resize tiếp theo sao chép 2k phần tử: dùng hết 2k đơn vị.
- Tài khoản không bao giờ âm.

Amortized cost = 3 = O(1) mỗi add().

3.3 Phương pháp thế năng — Đo "tiềm năng nợ"

Định nghĩa hàm Φ(trạng thái) đo lượng "công nợ tích lũy" trong cấu trúc dữ liệu. Amortized cost được tính:

amortized_cost(op) = actual_cost(op) + ΔΦ
                   = actual_cost(op) + Φ(sau) - Φ(trước)

Với mảng động: Φ = 2 × size - capacity.

• Sau resize: size = k, capacity = 2k → Φ = 2k - 2k = 0.
• Mỗi add() không resize: size tăng 1, capacity không đổi → ΔΦ = 2.
• Amortized cost = 1 (insert) + 2 (ΔΦ) = 3.

Khi resize xảy ra (tại size = k = capacity):

• actual_cost = k (sao chép k phần tử).
• Φ_trước = 2k - k = k.
• Φ_sau = 2(k+1) - 2(k+1) = 0 (capacity mới = 2(k+1)).
• ΔΦ = 0 - k = -k.
• Amortized cost = k + (-k) + 1 = 1.

Cả hai trường hợp đều cho amortized cost = O(1). Phương pháp thế năng mạnh hơn tổng hợp/kế toán khi cần phân tích cấu trúc dữ liệu phức tạp hơn.

Đây là pseudocode logic grow của mảng động:

-- Mở rộng mảng nội bộ khi đầy.
-- oldCapacity >> 1 là dịch bit phải 1: tương đương chia 2.
-- newCapacity = oldCapacity + oldCapacity/2 = 1.5 * oldCapacity.
grow(A, minCapacity):
    oldCapacity <- A.capacity
    newCapacity <- oldCapacity + (oldCapacity >> 1)   -- factor 1.5x
    newArray <- allocate(newCapacity)
    copy(A.data, newArray, A.size)
    A.data <- newArray
    A.capacity <- newCapacity

Time: O(n)  Space: O(n) -- sao chép n phần tử

4. Vì sao 1.5x — không phải 2x hay 1.1x

Growth factor ảnh hưởng đến hai thứ đối lập:

• Factor lớn → ít lần resize → ít sao chép → tốt cho thời gian. Nhưng waste nhiều RAM.
• Factor nhỏ → ít waste RAM. Nhưng resize liên tục → nhiều sao chép.

2x là lựa chọn classic trong CS textbook, phép tính đơn giản cho phân tích tổng hợp. Một số thư viện chuẩn C++ dùng 2x.

1.5x là lựa chọn của Java ArrayList và MSVC. Lý do kỹ thuật quan trọng:

Với grow factor r, dãy capacity là: 1, r, r², r³, ...

Khi block cũ được giải phóng (sau resize), tổng dung lượng của tất cả block cũ bằng: 1 + r + r² + ... + r^(k-1) = (r^k - 1) / (r - 1)

Block mới cần dung lượng r^k. Để block mới có thể tái sử dụng vùng nhớ của tất cả block cũ (allocator có thể tái dùng), cần:

(r^k - 1) / (r - 1) >= r^k

Đơn giản hóa: điều này xảy ra khi r nhỏ hơn golden ratio φ ≈ 1.618. Với r = 2: tổng block cũ bằng đúng r^k - 1 — chỉ thiếu 1 đơn vị để đủ. Về lý thuyết, OS allocator không thể gộp lại kịp. Với r = 1.5: tổng block cũ vượt yêu cầu sau vài lần resize — allocator có thể tái dùng.

1.1x thì resize quá thường xuyên — với 1 triệu phần tử cần hàng trăm lần resize thay vì vài chục.

5. Sơ đồ chi phí resize

xychart-beta
    title "Chi phí mỗi lần add() — spike khi resize"
    x-axis ["add 1", "add 2", "add 3", "add 4", "add 5", "add 6", "add 7", "add 8", "add 9"]
    y-axis "Chi phí (đơn vị)" 0 --> 9
    bar [1, 2, 3, 1, 5, 1, 1, 1, 9]

6. Pitfall — Khi amortized không đủ

Pitfall 1: Amortized sụp đổ khi bạn ép thao tác đắt liên tiếp.

Nếu workload insert tới ngưỡng resize rồi xóa vài phần tử, insert lại đến ngưỡng resize, rồi xóa... Mỗi vòng lặp đều trigger resize. Amortized O(1) dựa trên giả định rằng n thao tác đắt được "trả" bởi nhiều thao tác rẻ trước đó — nhưng nếu thao tác đắt xảy ra liên tục, giả định đó không còn đúng.

-- Trường hợp bệnh lý: insert đến ngưỡng, remove, insert, remove...
-- Mỗi vòng trigger resize. Đảm bảo amortized KHÔNG giữ.
-- capacity = 8
for round <- 1 đến 1000:
    while list.size < 8: list.add(0)    -- điền đầy đến capacity
    list.remove(list.size - 1)          -- giảm xuống dưới ngưỡng
    list.add(0)                         -- trigger resize mỗi lần
    list.remove(list.size - 1)          -- remove lại

Nếu biết trước size tối đa, dùng new ArrayList<>(initialCapacity) để tránh resize hoàn toàn.

Pitfall 2: Real-time và latency-sensitive code — worst case quan trọng hơn amortized.

Amortized O(1) nghĩa là trung bình tốt. Nhưng lần tệ nhất vẫn là O(n) — và nó sẽ xảy ra. Với:

• UI rendering: resize mảng trong render loop gây frame drop.
• Audio buffer: spike latency làm vỡ audio stream.
• HFT: resize trong hot path có thể trượt time window.

Trong các context đó, pre-allocate với capacity đã biết để loại bỏ resize hoàn toàn. Amortized O(1) tốt cho throughput, không tốt cho jitter.

Pitfall 3: Không nhầm amortized với average.

Average case phụ thuộc distribution của input. Amortized là đảm bảo trên worst-case sequence. QuickSort có average case O(n log n) nhưng không có amortized O(n log n) — vì tồn tại dãy input cụ thể (đã sorted, hoặc adversarial pivot) luôn trigger worst case. Mảng động thực sự có amortized O(1) — không cần giả định gì về input.

7. Ứng dụng thực tế

Mảng động trong OpenJDK

Bit shift >> 1 tương đương chia 2. Cộng lại: oldCapacity + oldCapacity / 2 = 1.5 × oldCapacity. Xem source ArrayList.java tại GitHub OpenJDK để thấy edge case overflow khi oldCapacity rất lớn.

Bảng băm resize

Load factor mặc định 0.75: khi size > 0.75 × capacity, bảng băm tăng gấp đôi capacity. Tương tự mảng động, resize là O(n) nhưng amortized O(1). Sau khi treeify: bucket vượt ngưỡng node → chuyển thành cây đỏ-đen, lookup giảm từ O(n) worst case xuống O(log n).

StringBuilder

Internal mảng ký tự grow tương tự mảng động — thường dùng 2x khi đầy. Đây là lý do nối chuỗi bằng StringBuilder trong vòng lặp nhanh hơn dùng toán tử + rất nhiều:

-- O(n²) tổng: mỗi lần + tạo một chuỗi mới, sao chép tất cả ký tự đã có
result <- ""
for i <- 0 đến n-1:
    result <- result + "x"      -- tạo chuỗi mới mỗi lần, sao chép toàn bộ

-- O(n) tổng: StringBuilder tái dùng mảng nội bộ, chỉ sao chép khi resize
sb <- StringBuilder rỗng
for i <- 0 đến n-1:
    sb.append("x")              -- amortized O(1) mỗi lần gọi
result <- sb.toString()         -- một lần sao chép cuối cùng

Nối chuỗi bằng + tạo chuỗi mới mỗi lần — chi phí sao chép tích lũy thành O(n²) cho n lần ghép. StringBuilder dùng grow strategy giống mảng động, tổng chi phí O(n).

Deque vòng tròn

Deque dùng mảng circular với capacity là lũy thừa của 2. Khi đầy, double capacity và sao chép phần tử. Amortized O(1) cho cả thêm vào đầu lẫn cuối. Được dùng làm Stack và Queue chuẩn trong nhiều ngôn ngữ — nhanh hơn danh sách liên kết vì cache-friendly (mảng liên tục).

8. 📚 Deep Dive tài liệu gốc

9. Tóm tắt

• Amortized là trung bình chi phí trên dãy thao tác worst-case — mạnh hơn average case (không cần giả định distribution).
• Ba phương pháp: tổng hợp (tính tổng / n), kế toán (trả trước vào tài khoản), thế năng (hàm Φ đo nợ tích lũy). Cả ba cho cùng kết quả cho cùng cấu trúc.
• add() amortized O(1): tổng n lần add tốn dưới 2n — mỗi op trung bình O(1), dù từng lần resize tốn O(n).
• 1.5x growth được chọn vì tổng dung lượng block cũ đủ để allocator tái sử dụng (cần factor nhỏ hơn golden ratio ≈ 1.618), đồng thời ít waste RAM hơn 2x.
• Amortized không áp dụng khi workload ép thao tác đắt liên tục (adversarial sequence) — dùng initialCapacity khi biết trước size.
• Real-time code: worst case per op quan trọng hơn amortized — spike 10ms khi resize có thể drop frame hoặc miss audio buffer.
• Nối chuỗi bằng + trong vòng lặp là O(n²) vì tạo chuỗi mới mỗi lần. StringBuilder amortized O(1) → tổng O(n).

10. Tự kiểm tra

Bài tiếp theo: Memory model & cache locality