Beberapa struktur data memiliki operasi yang biasanya cepat (O(1)) tetapi kadang mahal (O(n)). std::vector::push_back adalah contoh klasik: biasanya menambah elemen pada slot kosong (O(1)), tetapi bila kapasitas penuh, perlu realokasi O(n). Bila kita hanya melihat worst case per operasi, kita akan menyatakan push_back sebagai O(n) — padahal dalam penggunaan normal, rata-rata biayanya jauh lebih murah. Analisis amortisasi memberi kerangka formal untuk pernyataan seperti “push_back adalah O(1) amortized”. Pada Chapter ini kita akan mempelajari tiga metode analisis amortisasi: aggregate, accounting, dan potential method.

Konsep Dasar Amortisasi #

Analisis amortisasi menjawab pertanyaan: “Berapa rata-rata biaya per operasi, bila dilakukan sekumpulan operasi secara berurutan?”.

Diberikan urutan n operasi, total biaya seluruh operasi adalah T(n). Maka biaya amortized per operasi adalah T(n) / n.

Berbeda dengan average case (yang mengasumsikan distribusi input), amortisasi memberi jaminan untuk setiap urutan operasi yang valid, terlepas dari distribusinya.

NotasiWorst case per opAmortized per op
std::vector::push_backO(n)O(1)
std::vector::pop_backO(1)O(1)
std::vector::operator[]O(1)O(1)
Multipop stack (k elemen)O(k)O(1)
Binary counter incrementO(k) (k = banyak bit)O(1)

Metode 1: Aggregate Method #

Cara paling sederhana: hitung total biaya seluruh operasi, lalu bagi dengan n.

Contoh: Multipop Stack #

Misalkan stack dengan operasi:

  • push(x) — O(1)
  • pop() — O(1)
  • multipop(k) — mempop min(k, size) elemen — O(min(k, size))

Worst case per operasi: multipop(n) bisa O(n). Tapi bila kita lakukan n operasi (campuran push, pop, multipop), total elemen yang dipush paling banyak n. Setiap elemen hanya bisa dipop (atau multipop) satu kali. Maka total operasi pop + multipop ≤ n, dan total push ≤ n. Total biaya ≤ 2n. Amortized per operasi: 2n / n = O(1). ∎

Metode 2: Accounting Method #

Accounting method memberi “biaya” (charge) berbeda untuk setiap operasi: lebih besar dari biaya aktual, sisanya disimpan sebagai “kredit” untuk dipakai nanti saat operasi mahal.

Contoh: Binary Counter Increment #

Misalkan kita penghitung biner 8-bit yang dimulai dari 00000000. Operasi increment menambah counter sebesar 1.

Mekanisme: setiap bit yang berubah dari 1 → 0 saat flip memerlukan 1 operasi; bit yang berubah dari 0 → 1 memerlukan 1 operasi. Pada increment biasa, hanya 1 bit berubah (rightmost 0 → 1). Pada increment dari 01111111 → 10000000, 8 bit berubah.

Charge amortized: tetapkan biaya 2 per increment. Biaya aktual 1 untuk flip 0 → 1, sisanya 1 disimpan sebagai kredit untuk membayar flip 1 → 0 nanti.

Bukti: setiap bit 1 di counter memiliki 1 kredit tersimpan. Saat flip 1 → 0 terjadi, kredit tersebut dipakai. Total kredit tidak pernah negatif, sehingga total biaya aktual ≤ total biaya amortized. Amortized per increment: O(1). ∎

Metode 3: Potential Method #

Potential method menggunakan “fungsi potensial” Φ(D) yang memetakan state struktur data D ke bilangan real non-negatif. Potensial merefleksikan “energi tersimpan” yang bisa dipakai untuk membayar operasi mahal di masa depan.

Biaya amortized operasi ke-i:

text 
â_i = c_i + Φ(D_i) - Φ(D_{i-1})

dengan c_i biaya aktual dan D_i state setelah operasi ke-i.

Contoh: std::vector::push_back dengan Strategi Doubling #

std::vector menyimpan elemen pada array dinamis. Saat push_back dan kapasitas penuh, vektor mengalokasikan array baru berkapasitas 2 kali lama, menyalin semua elemen, lalu membebaskan array lama. Strategi doubling ini memberi amortized O(1).

Potensial: Φ(D) = 2·size - capacity (untuk size ≥ capacity/2), 0 untuk size < capacity/2.

Analisis:

  • Bila size < capacity (kasus normal): c_i = 1 (satu insert). Perubahan potensial ΔΦ = 2 (size bertambah 1). Amortized â = 1 + 2 = 3.
  • Bila size == capacity (realokasi): c_i = n + 1 (salin n elemen + insert baru). Setelah realokasi, size = n+1, capacity = 2n. Φ_before = 2n - n = n, Φ_after = 2(n+1) - 2n = 2. ΔΦ = 2 - n. Amortized â = (n+1) + (2 - n) = 3.

Dengan demikian, setiap push_back berbiaya amortized konstan 3. ∎

Kode: Verifikasi Eksperimen Amortized push_back #

cpp 
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    long long totalOperasi = 0;
    int realokasi = 0;

    int n = 1000;
    for (int i = 0; i < n; ++i) {
        std::size_t kap = v.capacity();
        v.push_back(i);
        if (v.capacity() != kap) ++realokasi;
        totalOperasi += 1;                  // biaya insert
    }

    std::cout << "n=" << n << '\n';
    std::cout << "Total insert       : " << n << '\n';
    std::cout << "Jumlah realokasi  : " << realokasi << '\n';
    std::cout << "Kapasitas akhir    : " << v.capacity() << '\n';
    std::cout << "Biaya total (n)"   << " : " << totalOperasi << '\n';
    std::cout << "Amortized per op   : "
              << static_cast<double>(totalOperasi) / n << '\n';

    // Verifikasi: total biaya dengan salin saat realokasi
    long long totalDenganSalin = n;     // n insert
    long long totalSalin = 0;
    for (long long kap = 1; kap < n; kap *= 2) {
        totalSalin += kap;              // setiap doubling menyalin elemen
    }
    totalDenganSalin += totalSalin;
    std::cout << "Biaya real (insert + salin) : " << totalDenganSalin << '\n';
    std::cout << "Amortized real per op       : "
              << static_cast<double>(totalDenganSalin) / n << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
n=1000
Total insert       : 1000
Jumlah realokasi  : 11
Kapasitas akhir    : 1024
Biaya total (n) : 1000
Amortized per op   : 1
Biaya real (insert + salin) : 2023
Amortized real per op       : 2.023

Bedah Kode Baris-per-Baris #

  1. Baris std::vector<int> v;: vektor kosong dengan kapasitas awal 0 (atau kecil, tergantung implementasi).
  2. Baris if (v.capacity() != kap) ++realokasi;: mendeteksi realokasi dengan membandingkan kapasitas sebelum dan sesudah push_back. Setiap perubahan kapasitas menandakan realokasi.
  3. Baris totalOperasi += 1;: menghitung biaya satu insert sebagai 1 unit. Ini belum memperhitungkan biaya salin saat realokasi.
  4. Baris for (long long kap = 1; kap < n; kap *= 2): menjumlahkan elemen yang disalin pada setiap doubling: 1 + 2 + 4 + ... + 512 = 1023. Untuk n = 1000, total salin 1023, sehingga total biaya real 1000 + 1023 = 2023.
  5. Output: jumlah realokasi untuk n = 1000 adalah 11 (kapasitas vektor bertumbuh 1, 2, 4, …, 1024). Biaya amortized real 2.023 per operasi — konstan, hanya sedikit lebih dari 2. Inilah inti klaim “push_back adalah O(1) amortized”.

Kapan Amortisasi Penting #

Analisis amortisasi sangat berguna ketika:

  • Operasi tunggal memiliki worst case tinggi tetapi jarang terjadi pada urutan operasi yang realistis.
  • Struktur data dirancang untuk penggunaan berulang (bukan panggilan satu kali).
  • Sistem real-time tidak ada; toleransi terhadap latensi sesekali masih dapat diterima.
Struktur/OperasiWorst case per opAmortized per op
std::vector::push_backO(n) (realokasi)O(1)
std::string::append (small string opt)O(n)O(1)
std::unordered_map::insert (rehash)O(n)O(1)
Disjoint Set Union (with path compression + union by rank)O(log n)O(α(n)) (hampir O(1))
Splay tree (semua operasi)O(n)O(log n)

Ringkasan #

  • Amortisasi memberi rata-rata biaya per operasi pada urutan n operasi, terlepas dari distribusi input.
  • Tiga metode utama: aggregate (hitung total lalu bagi), accounting (charge lebih banyak, simpan sisanya), potential (gunakan fungsi potensial untuk menyerap biaya mahal).
  • std::vector::push_back dengan strategi doubling memiliki amortized O(1) per operasi, meskipun worst case per operasi O(n).
  • Amortisasi cocok untuk struktur data yang dirancang penggunaan berulang; tidak menghapus worst case individual.

Pada Chapter berikutnya kita akan merangkum seluruh kelas kompleksitas yang telah kita pelajari dan membandingkannya satu sama lain dengan tabel referensi komprehensif.