Amortized analysis — Vì sao ArrayList.add() là O(1) dù đôi khi tốn O(n)

Bạn benchmark ArrayList.add() một triệu lần. Đ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 ArrayList phải resize nội mảng.

Vậy 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). Javadoc 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. ArrayList.add() worst case là O(n) — khi xảy ra resize, phải copy 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 HashMap.get(), tài liệu nói "amortized O(1)" — thực ra là average case với assumption hash function tốt (như bài 01 đã đề cập). ArrayList 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 Aggregate method — Đế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 ArrayList với grow factor 2x, bắt đầu từ capacity 1:

n add() operations:
- add() #1: capacity = 1, no resize. Cost = 1.
- add() #2: resize from 1 to 2, copy 1 element. Cost = 1 + 1 = 2.
- add() #3: resize from 2 to 4, copy 2 elements. Cost = 1 + 2 = 3.
- add() #5: resize from 4 to 8, copy 4 elements. Cost = 1 + 4 = 5.
- Most add() calls: no resize. Cost = 1.

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

• Copy cost (tổng cộng): 1 + 2 + 4 + 8 + ... + n/2 — chuỗi hình học bằng n - 1.
• Insert cost: 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 aggregate phù hợp khi tổng chi phí có dạng đơn giản để tính.

3.2 Accounting method — 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 ArrayList 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í copy bản thân khi resize sau này.
• 1 đơn vị trả trước cho copy một phần tử cũ khi resize.

Tại sao 3 don vi la du?

Sau khi resize len capacity = 2k (tu k):
- Co k phan tu can copy.
- Cac add() tiep theo: k lan add truoc khi resize tiep.
- Moi lan add tich 2 don vi vao account -> k * 2 = 2k don vi.
- Resize tiep theo copy 2k phan tu: dung het 2k don vi.
- Account khong bao gio am.

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

3.3 Potential method — Đo "tiềm năng nợ"

Định nghĩa hàm Φ(state) đ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) + Φ(after) - Φ(before)

Với ArrayList: Φ = 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 (copy k phần tử).
• Φ_before = 2k - k = k.
• Φ_after = 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). Potential method mạnh hơn aggregate/accounting khi cần phân tích cấu trúc dữ liệu phức tạp hơn.

Đây là đoạn grow logic của ArrayList trong OpenJDK:

// Simplified from OpenJDK ArrayList.java (around line 245-270)
// oldCapacity + (oldCapacity >> 1) = 1.5x growth
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity, // min growth
            oldCapacity >> 1           // preferred growth = 0.5 * oldCapacity
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

oldCapacity >> 1 là bit shift phải 1 bit — tương đương chia 2. Cộng lại: oldCapacity + oldCapacity / 2 = 1.5 * oldCapacity.

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 copy → 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 copy.

2x là lựa chọn classic trong CS textbook, simple math cho aggregate analysis. std::vector trong C++ (libc++) và StringBuilder trong nhiều JVM dùng 2x.

1.5x là lựa chọn của Java ArrayList và MSVC std::vector. 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 vào: 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. Pitfall — Khi amortized không đủ

Pitfall 1: Amortized sụp đổ khi bạn ép op đắ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 op đắt xảy ra liên tục, giả định đó không còn đúng.

// Pathological case: insert to threshold, remove, insert, remove...
List<Integer> list = new ArrayList<>(8); // capacity 8
for (int round = 0; round < 1000; round++) {
    while (list.size() < 8) list.add(0);   // fill to capacity
    list.remove(list.size() - 1);          // drop below threshold
    list.add(0);                           // triggers resize every time
    list.remove(list.size() - 1);          // remove again
}
// Each add() near threshold triggers O(n) resize. Amortized guarantee does NOT hold
// because the sequence is adversarially crafted to always hit the expensive path.

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 ArrayList 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 đó, dùng int[] hoặc new ArrayList<>(knownCapacity) để 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. ArrayList.add() thực sự có amortized O(1) — không cần giả định gì về input.

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

ArrayList.grow() — Java OpenJDK source

oldCapacity + (oldCapacity >> 1) tại ArrayList.java dòng ~245 trên GitHub. Bit shift >> 1 cho phép tính 1.5x mà không cần phép chia. ArraysSupport.newLength() xử lý edge case overflow khi oldCapacity rất lớn.

HashMap resize

Load factor mặc định 0.75: khi size > 0.75 * capacity, HashMap double capacity. Tương tự ArrayList, resize là O(n) nhưng amortized O(1). Java 8 thêm treeify: bucket vượt 8 node → chuyển thành red-black tree, lookup giảm từ O(n) worst case xuống O(log n). Amortized vẫn O(1) nhưng constant tăng một chút do overhead quản lý tree.

StringBuilder.append()

Internal char[] grow tương tự ArrayList — 2x khi đầy. Đây là lý do StringBuilder.append() trong loop nhanh hơn String += rất nhiều:

// O(n^2) total: each += creates a new String object, copies all chars so far
String result = "";
for (int i = 0; i < 10000; i++) {
    result += "x"; // new String allocation + copy every iteration
}

// O(n) total: StringBuilder reuses internal char[], only copies on resize
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append("x"); // amortized O(1) per call
}
String result2 = sb.toString(); // one final copy

String += s tạo String mới mỗi lần — chi phí copy tích lũy thành O(n²) cho n lần ghép. StringBuilder dùng grow strategy giống ArrayList, tổng chi phí O(n).

ArrayDeque resize

ArrayDeque dùng mảng circular với capacity là power-of-two. Khi đầy, double capacity và copy phần tử. Amortized O(1) cho cả addFirst() và addLast(). Được dùng làm Stack và Queue chuẩn trong Java — nhanh hơn LinkedList vì cache-friendly (mảng liên tục).

C++ std::vector

libc++ (Clang) dùng 2x, MSVC dùng 1.5x — cùng tradeoff RAM vs resize frequency. Cả hai đều có amortized O(1) push_back. GCC libstdc++ dùng 2x. Tương tự question khi chọn Java container: với embedded/constrained memory, 1.5x ít waste hơn.

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

8. 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: aggregate (tính tổng / n), accounting (trả trước vào tài khoản), potential (hàm Φ đo nợ tích lũy). Cả ba cho cùng kết quả cho cùng cấu trúc.
• ArrayList.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 op đắ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.
• String += trong loop là O(n²) vì tạo String mới mỗi lần. StringBuilder.append() amortized O(1) → tổng O(n).

9. Tự kiểm tra

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