Analisis diamortisasi? (Jaminan Kinerja Kasus Terburuk)

Apa itu Analisis Amortisasi? Dan bagaimana itu bisa membantu saya mencapai jaminan kinerja terburuk dalam program saya?

Saya membaca bahwa teknik-teknik berikut ini dapat membantu programmer mencapai jaminan kinerja terburuk (yaitu dengan kata-kata saya sendiri: menjamin bahwa waktu menjalankan suatu program tidak akan melebihi waktu berjalan dalam pemeran terburuk):

• Algoritma acak (misalnya algoritma quicksort kuadrat dalam kasus terburuk, tetapi memesan input secara acak memberikan jaminan probabilistik bahwa waktu yang berjalan adalah linearitmik)
• Urutan operasi (analisis kami harus memperhitungkan data dan urutan operasi yang dilakukan oleh klien)
• Analisis Amortisasi (cara lain untuk memberikan jaminan kinerja adalah dengan mengamortisasi biaya, dengan melacak total biaya semua operasi, dibagi dengan jumlah operasi. Dalam pengaturan ini, kami dapat memungkinkan beberapa operasi mahal, sambil menjaga biaya rata-rata operasi yang rendah. Dengan kata lain, kami menyebarkan biaya beberapa operasi yang mahal, dengan menugaskan sebagian untuk masing-masing sejumlah besar operasi yang tidak mahal)

Penulis menyebutkan penggunaan mengubah ukuran struktur data array untuk Stack sebagai salah satu contoh bagaimana mencapai analisis diamortisasi tapi saya masih tidak mengerti apa itu analisis diamortisasi, dan bagaimana sebenarnya dapat diimplementasikan (struktur data? Algoritma?) Untuk mencapai yang terburuk Jaminan kinerja -cast

Anda tidak menerapkan analisis diamortisasi. Ini adalah teknik untuk mendapatkan Obatasan yang lebih akurat .

Pengamatan penting yang harus Anda lakukan adalah, bahwa operasi mahal tidak dapat terjadi kapan saja.

Dalam kasus struktur data yang didukung array, array perlu mengubah ukuran setiap saat - saat penuh. Ini adalah operasi yang paling mahal dan membutuhkan O(n)waktu. Semua sisipan lain ke dalam array adalah O(1).

Untuk menentukan runtime untuk memasukkan nitem, Anda dapat mengalikan ndengan operasi O(n)yang paling mahal , yang menghasilkan perilaku runtime keseluruhan O(n^2).

Namun, ini tidak akurat karena mengubah ukuran tidak dapat terjadi sangat sering.

Ketika berbicara tentang uang, Anda mengamortisasi biaya, ketika Anda melunasi hutang Anda dengan beberapa pembayaran kecil seiring waktu.

Kita dapat menggunakan model ini untuk memikirkan algoritma juga. Kami hanya mengganti "waktu" dengan "uang" untuk menghindari pemetaan mental.

Setelah array terisi panjangnya n, kita bisa menggandakan ukurannya. Kita perlu melakukan operasi berikut:

• Alokasikan 2npotongan memori
• menyalin nitem

Jika kita mengasumsikan bahwa kedua mengalokasikan memori dan penyalinan terjadi dalam waktu linier, ini akan menjadi operasi yang sangat mahal. Namun, kami sekarang dapat menggunakan ide hutang dan mengamortasinya untuk analisis kami. Hanya saja, kita akan mengamortisasi hutang kita sebelum kita benar-benar membuatnya.
Mari kita asumsikan, bahwa saldo kita (uang / waktu) kembali ke 0 (yaitu kita tidak memiliki hutang atau kita memiliki sisa) setelah kita mengubah ukuran array.

Ini memiliki implikasi berikut:

• Memasukkan nitem berikutnya akan mencakup biaya pengubahan ukuran dan penyalinan (kami telah nmenggunakan slot, dan slot yang ntidak digunakan`)

Kita sekarang dapat berpikir tentang berapa banyak setiap operasi insert perlu membayar:

• Sisipan
• Biaya mengalokasikan satu keping memori
• biaya pemindahan ke memori yang baru dialokasikan

Kami sekarang telah menutupi biaya untuk mengalokasikan memori, menyalin dan memasukkan nelemen berikutnya . Namun, kami belum mengabaikan mengalokasikan ruang untuk nelemen lama serta menyalinnya.

Kami hanya mendistribusikan biaya nelemen lama kami ke elemen baru kami (belum dimasukkan) n:

• Biaya mengalokasikan satu keping memori
• biaya pemindahan ke memori yang baru dialokasikan

Secara total, setiap, setiap operasi penyisipan akan dikenakan biaya 5 unit. Ini membayar untuk penyisipannya sendiri, dan memindahkan dan mengalokasikan ruang untuk dirinya sendiri dan salah satu elemen lama.

Setiap operasi penyisipan masih membutuhkan waktu yang konstan, tetapi ukurannya terjadi secara gratis: Kami diamortisasi dengan menghabiskan waktu "lebih banyak" pada setiap penyisipan.

Akibatnya, memasukkan nelemen membutuhkan O(n)waktu.

Teknik lain untuk analisis diamortisasi dijelaskan di sini .

Pertama-tama: Ini adalah teknik untuk menganalisis runtime program, bukan teknik implementasi untuk algoritma.

Contoh yang disebutkan dalam daftar Anda adalah yang baik: Menambahkan item tunggal ke struktur data yang didukung array. Untuk setiap operasi penambahan tunggal, kasus terburuk adalah harus menyalin semua item yang ada. Analisis semacam itu terlalu pesimistis, karena Anda tidak harus melakukan itu jika Anda menggunakan strategi mengubah ukuran yang waras (mengalikan ukuran dengan beberapa x> 1,0). Analisis kemudian mengatakan Anda memiliki O (n ^ 2) terikat - O (n) per item kali n item - sedangkan runtime yang sebenarnya hanya O (n).

Jika Anda meratakan biaya pengubahan ukuran untuk semua item yang disisipkan (yang sebagian besar tidak perlu diubah ukurannya) Anda melakukan analisis diamortisasi. Analisis diamortisasi menghasilkan batas O (n) yang cocok dengan perilaku aktual algoritma.