Python - Analisis Amortisasi
Analisis diamortisasi melibatkan estimasi run time untuk urutan operasi dalam suatu program tanpa mempertimbangkan rentang distribusi data dalam nilai input. Contoh sederhananya adalah menemukan nilai dalam daftar yang diurutkan lebih cepat daripada dalam daftar yang tidak diurutkan. Jika daftar sudah diurutkan, tidak peduli seberapa terdistribusi datanya. Tetapi tentu saja panjang daftar memiliki pengaruh karena menentukan jumlah langkah yang harus dilalui algoritme untuk mendapatkan hasil akhir.
Jadi kita melihat bahwa jika biaya awal dari satu langkah untuk mendapatkan daftar yang diurutkan tinggi, maka biaya langkah-langkah selanjutnya untuk menemukan elemen menjadi sangat rendah. Jadi, analisis yang diamortisasi membantu kami menemukan batasan pada kasus terburuk waktu berjalan untuk urutan operasi. Ada tiga pendekatan untuk analisis diamortisasi.
Accounting Method- Ini melibatkan penetapan biaya untuk setiap operasi yang dilakukan. Jika operasi aktual selesai lebih cepat dari waktu yang ditetapkan, maka beberapa kredit positif diakumulasikan dalam analisis. Dalam skenario sebaliknya, itu akan menjadi kredit negatif. Untuk melacak akumulasi kredit ini, kami menggunakan struktur data tumpukan atau pohon. Operasi yang dilakukan lebih awal (seperti menyortir daftar) memiliki biaya perolehan diamortisasi yang tinggi tetapi operasi yang terlambat berurutan memiliki biaya perolehan diamortisasi yang lebih rendah karena akumulasi kredit digunakan. Jadi biaya perolehan diamortisasi adalah batas atas dari biaya sebenarnya.
Potential Method- Dalam metode ini, kredit yang disimpan digunakan untuk operasi masa depan sebagai fungsi matematika dari keadaan struktur data. Evaluasi fungsi matematika dan biaya diamortisasi harus sama. Jadi bila biaya sebenarnya lebih besar dari biaya perolehan diamortisasi ada penurunan potensi dan digunakan untuk operasi masa depan yang mahal.
Aggregate analysis - Dalam metode ini kami memperkirakan batas atas pada total biaya n langkah. Biaya perolehan diamortisasi adalah pembagian sederhana dari total biaya dan jumlah langkah (n) ..