Amortized Analysis

Beberapa struktur data punya operasi yang kadang-kadang lambat (mis. push_back pada std::vector saat capacity penuh perlu realokasi O(n)) tetapi biasanya cepat (O(1)). Worst case analysis memberi gambaran pesimis: setiap push_back dianggap O(n), padahal rata-rata O(1). Amortized analysis memberi jawaban tengah: rata-rata biaya per operasi dalam sequence panjang. Tidak seperti average case (yang mengasumsikan distribusi input), amortized analysis menjamin biaya untuk sequence operasi apapun. Tiga metode klasik: aggregate, accounting (banker’s method), dan potential (physicist’s method). Pada Chapter ini kita membedah ketiganya pada kasus std::vector doubling, implementasi trace real, dan ekstensi ke operasi lain.

Aturan: Amortized ≠ Average Case #

Amortized analysis cocok untuk struktur data dinamis: dynamic array, splay tree, Fibonacci heap, dsb.

Mekanisme: Tiga Metode #

Metode 1: Aggregate #

Hitung total biaya T(n) untuk n operasi, lalu bagi: amortized = T(n) / n.

Contoh: push_back pada vector doubling capacity.

• Push ke-1: 1 (insert) + 1 (allocate initial cap=1) = 2.
• Push ke-2: 1 (insert) + 2 (copy existing + allocate cap=2) = 3.
• Push ke-3: 1 (insert) = 1.
• Push ke-4: 1 (insert) + 4 (copy + allocate) = 5.
• Push ke-5..7: 1 each.
• Push ke-8: 1 + 8 = 9.
• …
• Push ke-2^k: 1 + 2^k.

Total T(n) = Σ(i=1 to n) cost(i). Operasi mahal hanya terjadi di indeks pangkat 2. Total = n + Σ(k=0 to log n) 2^k = n + 2n - 1 = O(n). Amortized = O(n) / n = O(1).

Metode 2: Accounting (Banker’s) #

Bayar lebih untuk operasi murah, simpan “credit” untuk operasi mahal di masa depan.

• Biaya aktual push_back murah = 1. Bayar 3 (overpay 2).
• Biaya aktual push_back mahal (saat resize) = existing_size + 1. Credit yang tersimpan = 2 × existing_size (karena setiap elemen sudah dibayar overpay 2 saat insert). Bayar resize pakai credit.

Total credit pernah ≥ 0 → sequence valid. Amortized cost per operasi = 3 = O(1).

Metode 3: Potential (Physicist’s) #

Definisikan potential function Φ(D) pada state D struktur data. Φ(D_0) = 0 (initial state), Φ(D_i) ≥ 0 selalu.

Amortized cost a_i = c_i + Φ(D_i) - Φ(D_{i-1}) di mana c_i = actual cost.

Total amortized = Σ a_i = Σ c_i + Φ(D_n) - Φ(D_0) ≥ Σ c_i (karena Φ(D_n) ≥ 0 = Φ(D_0)).

Untuk vector doubling: pilih Φ(D) = 2 × size - capacity bila size > capacity/2, else Φ(D) = 2 × size - capacity (atau rumus serupa). Saat resize, potential drop membayar biaya copy. Amortized cost = O(1).

Implementasi Trace #

#include <iostream>
#include <vector>

// Dynamic array with doubling strategy
class DynamicArray {
public:
    DynamicArray() : data_(nullptr), capacity_(0), size_(0) {}
    ~DynamicArray() { delete[] data_; }

    void push_back(int val) {
        if (size_ == capacity_) {
            int new_cap = (capacity_ == 0) ? 1 : capacity_ * 2;
            int* new_data = new int[new_cap];
            for (int i = 0; i < size_; ++i) new_data[i] = data_[i];
            delete[] data_;
            data_ = new_data;
            capacity_ = new_cap;
            std::cout << "  resize: cap " << capacity_ / 2 << " -> " << capacity_ << '\n';
        }
        data_[size_++] = val;
    }

    int operator[](int i) const { return data_[i]; }
    int size() const { return size_; }
    int capacity() const { return capacity_; }

private:
    int* data_;
    int capacity_;
    int size_;
};

int main() {
    DynamicArray arr;
    std::cout << "Push 16 elemen, trace resize:\n";
    for (int i = 0; i < 16; ++i) {
        arr.push_back(i * 10);
    }

    std::cout << "\nSize: " << arr.size() << ", capacity: " << arr.capacity() << '\n';
    std::cout << "Isi: ";
    for (int i = 0; i < arr.size(); ++i) std::cout << arr[i] << ' ';
    std::cout << '\n';

    std::cout << "\n--- Analisis Amortized ---\n";
    std::cout << "Total operasi copy (for 16 push): 1 + 2 + 4 + 8 = 15 copies\n";
    std::cout << "Total operasi (16 push + 15 copy) = 31 = 2n - 1 = O(n)\n";
    std::cout << "Amortized per push: 2n / n = O(1)\n";
    return 0;
}

Output yang Dihasilkan:

Push 16 elemen, trace resize:
  resize: cap 0 -> 1
  resize: cap 1 -> 2
  resize: cap 2 -> 4
  resize: cap 4 -> 8
  resize: cap 8 -> 16

Size: 16, capacity: 16
Isi: 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 

--- Analisis Amortized ---
Total operasi copy (for 16 push): 1 + 2 + 4 + 8 = 15 copies
Total operasi (16 push + 15 copy) = 31 = 2n - 1 = O(n)
Amortized per push: 2n / n = O(1)

Bedah Kode Baris-per-Baris #

1. if (size_ == capacity_): cek apakah array penuh. Bila ya, perlu resize.
2. new_cap = (capacity_ == 0) ? 1 : capacity_ * 2: doubling strategy. Kapasitas baru = 2× kapasitas lama (atau 1 bila masih kosong). Trik growth_factor = 2 memberi amortized O(1). Bila growth_factor = 1.5 (mis. std::vector beberapa implementasi), amortized tetap O(1) tetapi konstanta sedikit berbeda.
3. int* new_data = new int[new_cap]: alokasi buffer baru.
4. for (int i = 0; i < size_; ++i) new_data[i] = data_[i]: copy elemen-elemen lama. Ini operasi O(size_) yang menyebabkan worst case O(n) untuk satu push_back bila resize terjadi.
5. delete[] data_; data_ = new_data;: dealokasi buffer lama, replace dengan baru.
6. data_[size_++] = val: insert elemen baru. O(1).
7. Trace resize: terjadi 5 kali untuk 16 push, pada size = 1, 2, 4, 8, 16. Total copy = 0 + 1 + 2 + 4 + 8 = 15. Total operasi = 16 (insert) + 15 (copy) = 31 = 2n - 1 = O(n).
8. Amortized = 31 / 16 ≈ 2 = O(1) per push.

Contoh Lain: Multipop Stack #

Stack dengan operasi push(x) O(1), pop() O(1), multipop(k) (pop k elemen sekaligus) yang O(min(k, size)). Worst case multipop = O(n).

Sequence n operasi: total biaya ≤ 2n (setiap elemen dipush dan dipop paling banyak sekali). Amortized = O(1) per operasi.

Contoh: Binary Counter #

Increment counter biner. Setiap increment() memflip beberapa bit. Worst case O(log n) bila semua bit flip (mis. 011...1 → 100...0).

Total biaya n increment = O(n) karena bit ke-i flip setiap 2^i increment. Sum = n/2 + n/4 + n/8 + ... = 2n = O(n). Amortized = O(1).

Kompleksitas Amortized pada Struktur Populer #

Ringkasan #

• Amortized analysis = biaya rata-rata per operasi dalam sequence, dijamin untuk sequence apapun.
• Tiga metode: aggregate (hitung total / n), accounting (overpay murah, kredit untuk mahal), potential (fungsi potential Φ(D)).
• Dynamic array doubling: amortized push_back = O(1) meskipun worst case O(n).
• Splay tree: amortized find/insert/delete = O(log n).
• DSU: amortized find/unite = O(α(n)).
• Amortized ≠ worst case. Untuk aplikasi real-time dengan latency terjamin, struktur worst-case O(1) tetap diperlukan.