Amortized analysis menghitung biaya rata-rata per operasi atas satu rangkaian operasi yang panjang, bukan biaya satu operasi saja. Contoh paling terkenal adalah push di array: sesekali satu push mahal, tapi kalau dirata-rata, tiap push tetap murah. Mirip kartu e-money: sekali antre lama untuk isi ulang, lalu puluhan kali tap cepat di gerbang tol.
🧪 Tebakan cepat: push ke-9 harus menyalin 8 isi lama. Kalau kamu push 12 kali, rata-rata biaya per push kira-kira 1, 2, atau 12? Tebak dulu, jawabannya ada di bagian "Rata-ratanya tetap di bawah 3".
Array dinamis: penuh, pindah ke array dua kali lebih besar
Array di JavaScript bisa membesar sendiri. Di balik layar, dia punya kapasitas (slot yang sudah disiapkan) dan size (slot yang sudah terisi). Selama masih ada slot kosong, push cuma menulis satu nilai: biayanya 1. Itu O(1): waktunya tetap, berapa pun banyak isinya. Kalau penuh, array bikin array baru dua kali lebih besar, menyalin semua isi lama, baru menulis nilai baru: biayanya size + 1. Itu O(n): isinya dua kali lipat, waktunya kira-kira dua kali lipat.
Ini 12 push ke array yang kapasitas awalnya 1, sama dengan Lab:
| Push ke- | Disalin | Kapasitas sesudahnya | Biaya |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 2 | 2 |
| 3 | 2 | 4 | 3 |
| 4 | 0 | 4 | 1 |
| 5 | 4 | 8 | 5 |
| 6 sampai 8 | 0 | 8 | 1 + 1 + 1 |
| 9 | 8 | 16 | 9 |
| 10 sampai 12 | 0 | 16 | 1 + 1 + 1 |
class DynamicArray {
constructor() {
this.capacity = 1;
this.size = 0;
this.storage = new Array(this.capacity);
}
push(value) {
let cost = 1;
if (this.size === this.capacity) {
this.capacity *= 2;
const bigger = new Array(this.capacity);
for (let i = 0; i < this.size; i++) {
bigger[i] = this.storage[i];
}
this.storage = bigger;
cost += this.size;
}
this.storage[this.size] = value;
this.size++;
return cost;
}
}
const arr = new DynamicArray();
for (let i = 1; i <= 5; i++) {
console.log(arr.push(i * 10));
}
// 1
// 2
// 3
// 1
// 5
this.size === this.capacityartinya penuh. Hanya saat itucapacitydigandakan dengan*= 2.- Loop
formenyalin semua isi lama kebigger, laluthis.storagediganti dengan array baru itu. Tanpa salinan ini, isi lama hilang. - Nilai baru selalu ditulis di
this.storage[this.size], lalusizebertambah satu, penuh atau gak. pushini mengembalikan biayanya (1 tulis + yang disalin), jadi hasilnya sama dengan kolom Biaya di tabel.
Rata-ratanya tetap di bawah 3
Total biaya 12 push: 12 tulis + 15 salinan (1 + 2 + 4 + 8) = 27. Rata-ratanya 27 / 12 = 2,25 per push. Itu jawaban tebakan: sekitar 2, bukan 12.
Kenapa tetap kecil? Tiap resize menyalin dua kali lebih banyak dari resize sebelumnya, tapi juga terjadi dua kali lebih jarang. Jumlah semua salinan untuk n push selalu kurang dari 2n, jadi total biayanya kurang dari 3n, dan rata-ratanya di bawah 3, sebesar apa pun n. 1.000 push totalnya 2.023, bukan 1.000 × 1.000.
Inilah arti "push itu amortized O(1)": kebanyakan push O(1), sesekali satu push O(n) karena resize, tapi rata-rata atas rangkaian push-nya tetap O(1).
Amortized, worst case, dan average case
| Istilah | Artinya | Contoh |
|---|---|---|
| Worst case | biaya paling mahal untuk satu operasi | satu push yang kena resize: O(n) |
| Average case | rata-rata kalau inputnya acak; input yang sial bisa lambat terus | cari di hash map: rata-rata O(1) kalau key-nya tersebar rata |
| Amortized | rata-rata per operasi atas rangkaian operasi apa pun, gak bergantung keberuntungan input | push di array dinamis: O(1) |
Jadi amortized dijamin untuk urutan operasi apa pun, sedangkan average case bergantung pada inputnya. Yang amortized O(1): push di array dinamis, set di hash map (sesekali rehash, yaitu pindah ke tabel yang lebih besar), dan union-find (hampir O(1)). Balanced BST (AVL, Red-Black) beda: tiap pencariannya dijamin O(log n), bukan O(1).
⚠️ Jebakan yang sering ketemu
- Amortized bukan jaminan per operasi. Satu push tetap bisa O(n). Di game atau audio yang butuh tiap langkah tepat waktu, satu resize besar bisa bikin patah-patah.
- Lupa menyalin isi lama. Kalau
storagelangsung diganti array kosong, semua isi sebelum resize hilang. - Kapasitas yang naik satu-satu. Kalau tiap penuh cuma ditambah 1 slot, setiap push kena resize, dan n push jadi O(n × n).
💡 Kenapa kali dua, bukan tambah 4? Kalau kapasitas cuma ditambah 4, resize terjadi tiap 4 push dan selalu menyalin semua isi. 1.000 push butuh sekitar 125.000 langkah, rata-rata 125 per push, dan makin besar n makin parah. Kali dua bikin resize makin jarang seiring array membesar, itu yang menjaga rata-ratanya tetap kecil.
TL;DR: Amortized analysis merata-ratakan biaya atas rangkaian operasi. Array dinamis yang penuh pindah ke array dua kali lebih besar dan menyalin semua isinya (O(n)), tapi resize makin jarang, jadi total n push kurang dari 3n: push itu amortized O(1). Worst case melihat satu operasi termahal, average case bergantung pada input acak, amortized dijamin untuk urutan operasi apa pun. Balanced BST dijamin O(log n) per operasi, bukan amortized O(1).
