Amortization

 Amortized analysis adalah metode yang digunakan untuk menunjukkan 

• waktu rata-rata yang diperlukan untuk melakukan satu urutan operasi pada struktur data terhadap keseluruhan operasi yang dilakukan.
• biaya rata-rata untuk satu operasi yang kemungkinan besar akan menjadi lebih kecil jika dilakukan pada suatu urutan operasi.
• kinerja rata-rata tiap operasi pada keadaan terburuk (worst case)

Ada 3 metode/ teknik dalam amortized analysis, yaitu:

1. Metode Aggregate
2. Metode Accounting
3. Metode Potential

Metode Aggregate

Pada metode ini, jika ditentukan upper bound biaya total suatu urutan n operasi adalah T(n), maka biaya amortized per operasi adalah T(n) per n.

Metode Accounting

Setiap operasi mempunyai biaya amortized yang spesifik. Operasi yang dilakukan pada urutan awal dapat diberi biaya yang lebih besar. Biaya tersebut selanjutnya akan menjadi "kredit prabayar" untuk digunakan pada operasi-operasi yang harganya lebih kecil dari biaya sebenarnya.

Metode Potential

Metode ini memiliki karakteristik seperti pada metode Accounting, tetapi kredit digunakan sebagai energi potensial pada struktur data.

Sumber:

"Amortized Analysis", Rully Soelaiman