Amortized Analysis

Jika Anda belajar library bernama "vector" di C++, maka mungkin Anda pernah mendengar bahwa kompleksitas push_back adalah amortized O(1). Apa yang dimaksud dengan amortized?

Penerjemahan langsung ke Bahasa Indonesia agak lucu, yaitu "dilunasi dengan angsuran". Untuk lebih memahaminya, lebih baik kita membahas contoh soalnya, yaitu push_back pada vector.

Permasalahan

Anda ingin membuat array, tetapi tidak mengetahui banyaknya elemen maksimal yang mungkin ditampung dalam suatu waktu. Salah satu cara yang dapat dilakukan adalah menggunakan "resize-able array".

Pertama mulai dengan sebuah array yang maksimal dapat menampung X elemen. Misalkan X kita beri nilai 10. Operasi menambahkan elemen di paling belakang awalnya array dapat dilakukan dengan cara kira-kira seperti ini:

Tentu saja ketika banyaknya elemen lebih dari 8, kita perlu memperbesar ukuran array-nya. Untuk sederhananya, kita gandakan ukuran array menjadi 16.

Pada bahasa C++, sayangnya alokasi memori array tidak dapat diperbesar. Terpaksa kita buat array yang baru dengan ukuran 16 elemen, lalu pindahkan isi array sebelumnya ke array yang baru. Teknik ini biasa disebut dengan "array doubling".

Kini kita dapat menampung sebanyak maksimal 16 elemen. Jika ternyata dibutuhkan lebih banyak, maka ukurannya akan terus diperbesar menjadi 32, 64, 128, dan seterusnya.

Pertanyaan: berapa kompleksitas appendElement?

Jawaban polosnya adalah kadang-kadang O(1), kadang-kadang O(N) dengan N adalah ukuran array pada saat itu.

Pertanyaan: mana yang lebih sering? O(1) atau O(N)?

Jika appendElement dilakukan sebanyak 128 kali, maka pada akhirnya ukuran array adalah 128. Array doubling terjadi pada saat ukuran array bernilai 8, 16, 32, dan 64.

Berarti terdapat 4 kali array doubling, dan 96 sisanya O(1).

Pertanyaan: apakah ini tidak efisien?

Sekilas terlihat tidak efisien, tetapi mari kita lihat dari sisi hitung-hitungan.

Seluruh proses array doubling membutuhkan 8 + 16 + 32 + 64 = 120 "operasi".
Bila dirata-rata, sebanyak 120 operasi dari 128 pemanggilan appendElement berarti terdapat 248/128 = 1.9 operasi per appendElement. Ternyata tidak terlalu buruk!


Perhitungan serupa juga dapat diamati untuk pemanggilan appendElement yang lebih banyak. Berikut grafik untuk rata-rata per operasi, sampai dengan pemanggilan appendElement ke-1 juta kali.

Dapat diperhatikan bahwa secara rata-rata, operasi appendElement membutuhkan 2 sampai 3 "operasi".

Cukup masuk akal, mengingat seluruh kerja keras untuk menyalin array ke array yang baru akan terbayar untuk sejumlah appendElement berikutnya. Bila appendElement sesudah yang ke-64 berlangsung lambat, maka 64 appendElement berikutnya akan berlangsung dalam O(1). Jadi seluruh kerja keras tersebut selalu terbayarkan (mungkin ini yang disebut dengan "dilunasi dengan angsuran").

Dapat dianggap bahwa "secara umum" appendElement adalah O(1). Istilah yang lebih tepat untuk menyebutnya adalah amortized O(1).

Contoh lain: queue dari 2 stack

Tahukah Anda bahwa Anda dapat membuat queue dari 2 buah stack? Mungkin tidak akan Anda gunakan untuk dunia nyata, tetapi memahami bagaimana hal ini dapat dilakukan dapat mengembangkan kreativitas.

Mari kita sebut kedua stack tersebut adalah stackPush dan stackPop. Pada kondisi awal, kedua stack kosong:

stackPush = []
stackPop = []

Setiap elemen yang di-push akan menempati stackPush. Contohnya kita melakukan push dengan elemen 1 dan 2.

stackPush = [1, 2]
stackPop = []

Untuk operasi pop, selalu ambil dari stackPop. Bila stackPop tidak kosong, cukup lakukan pop seperti biasa. Namun bila kosong, terlebih dahulu pindahkan seluruh elemen stackPush ke stackPop dengan urutan terbalik. Hal ini dapat dilakukan dengan satu per satu, pop stackPush dan push elemen tersebut ke stackPop. Hasil akhir yang dicapai adalah:

stackPush = []
stackPop = [2, 1]

Dapat Anda lihat bahwa elemen teratas adalah angka 1, yang mana merupakan elemen pertama. Operasi pop ini akan menghapus angka 1, yang memenuhi prinsip FIFO (First In First Out).

stackPush = []
stackPop = [2]

Mari kita lanjutkan dengan push 3, 4, dan 5.

stackPush = [3, 4, 5]
stackPop = [2]

Bila operasi pop dilakukan, angka 2 akan hilang dari stackPop.

stackPush = [3, 4, 5]
stackPop = []

Bila pop dilakukan lagi, maka seluruh elemen stackPush akan dipindahkan secara terbalik ke stackPop, menjadi:

stackPush = []
stackPop = [5, 4, 3]

Tentu saja operasi pop ini akan menghapus elemen 3 dari stackPop.

Setelah Anda memahami bagaimana struktur data ini bekerja, coba buktikan bahwa operasi pop bekerja dalam amortized O(1).

Contoh lain: splay tree

Pada struktur data splay tree, amortized analysis dapat diaplikasikan pada operasi "splay".

Sekilas info, splay tree adalah salah satu varian BBST. Operasi "splay" akan melakukan rotasi pada tree, sehingga elemen yang akan diakses/disisipkan/dihapus akan berada di root BST. Operasi ini kadang berlangsung cepat, kadang berlangsung lambat. Namun hasil perhitungan matematis menyatakan bahwa kompleksitas "splay" adalah amortized O(log N), dengan N adalah ketinggian dari pohonnya. Hal ini menyebabkan operasi insert/delete/lookup pada splay tree bekerja dalam amortized O(log N).

Dengan sifat ini, terkadang operasi pada splay tree berlangsung lebih lambat, meskipun masih dalam O(log N). Namun operasi yang lambat ini memungkinkan operasi-operasi berikutnya untuk berjalan dengan lebih cepat.

Penutup

Anda dapat membayangkan amortized analysis seperti menganalisis suatu pekerjaan berat yang memungkinkan sejumlah pekerjaan berikutnya menjadi lebih efisien.

Mengetahui amortized analysis membantu dalam hal memahami kompleksitas solusi Anda, terutama ketika menghadapi algoritma yang sifatnya "kadang-kadang cepat kadang-kadang lambat". Anda dapat mencoba melihatnya dari sisi secara keseluruhan, dan menimbang apakah lambatnya algoritma Anda berperan dalam "melunasi hutang" sehingga sejumlah operasi berikutnya menjadi efisien.