Waktu Diamortisasi Konstan

Jawaban:

776

Waktu diamortisasi dijelaskan dalam istilah sederhana:

Jika Anda melakukan operasi katakan jutaan kali, Anda tidak benar-benar peduli pada kasus terburuk atau terbaik dari operasi itu - yang Anda pedulikan adalah berapa banyak waktu yang diambil secara total ketika Anda mengulangi operasi itu sejuta kali .

Jadi tidak masalah jika operasi sangat lambat sesekali, selama "sesekali" cukup langka untuk kelambatan diencerkan. Waktu yang pada dasarnya diamortisasi berarti "waktu rata-rata yang diambil per operasi, jika Anda melakukan banyak operasi". Waktu diamortisasi tidak harus konstan; Anda dapat memiliki waktu diamortisasi linier dan logaritmik atau apa pun.

Mari kita ambil contoh mat dari array dinamis, yang berulang kali Anda tambahkan item baru. Biasanya menambahkan item membutuhkan waktu yang konstan (yaitu, O(1)). Tetapi setiap kali array penuh, Anda mengalokasikan dua kali lebih banyak ruang, menyalin data Anda ke wilayah baru, dan membebaskan ruang yang lama. Dengan asumsi mengalokasikan dan membebaskan berjalan dalam waktu yang konstan, proses pembesaran ini membutuhkan O(n)waktu di mana n adalah ukuran array saat ini.

Jadi setiap kali Anda memperbesar, Anda membutuhkan waktu sekitar dua kali lipat dari yang terakhir diperbesar. Tetapi Anda juga telah menunggu dua kali lebih lama sebelum melakukannya! Biaya setiap pembesaran dengan demikian dapat "tersebar" di antara sisipan. Ini berarti bahwa dalam jangka panjang, total waktu yang dibutuhkan untuk menambahkan item m ke array adalah O(m), dan waktu diamortisasi (yaitu waktu per penyisipan) adalah O(1).

Artelius
sumber
61
Hanya catatan dalam hal notasi: Waktu eksekusi konstan diamortisasi O (n) sering ditulis sebagai O (n) +, yang bertentangan dengan hanya O (n). Penambahan tanda tambah menunjukkan bahwa waktu eksekusi tidak dijamin menjadi O (n) dan benar-benar dapat melebihi waktu eksekusi.
Jeffpowrs
1
Dalam hal mengalokasikan ruang, apakah itu dari tumpukan?
berkomitmenandroider
3
Saya tidak setuju dengan "Anda tidak terlalu peduli dengan kasus terburuk". Itu tergantung pada use case. Jika pada akhirnya, Anda hanya tertarik pada hasil dari operasi 1 Juta yang dikutip, Anda tidak peduli. Tetapi jika itu adalah aplikasi waktu nyata, yang secara konstan membaca data dan kemudian menanggapinya, Anda mungkin memiliki masalah besar, jika memproses data tersebut membutuhkan 1 Juta kali lebih lama dari biasanya setelah setiap 1 Juta item data diproses!
Kai Petzke
2
@ Jeffe Powow Saya berpikir bahwa O (n) adalah waktu linier dan O (1) adalah waktu konstan . Jadi apakah itu berarti O (1) + akan menjadi waktu konstan diamortisasi dan O (n) + akan menjadi waktu linier diamortisasi ?
John Meyer
1
@JohnMeyer Ya.
Artelius
55

Ini berarti bahwa seiring waktu, skenario terburuk akan default ke O (1), atau waktu yang konstan. Contoh umum adalah array dinamis. Jika kami telah mengalokasikan memori untuk entri baru, menambahkannya akan menjadi O (1). Jika kami belum mengalokasikannya, kami akan melakukannya dengan mengalokasikan, katakanlah, dua kali lipat jumlah saat ini. Penyisipan khusus ini bukan O (1), melainkan sesuatu yang lain.

Yang penting adalah bahwa algoritma menjamin bahwa setelah urutan operasi operasi yang mahal akan diamortisasi dan dengan demikian membuat seluruh operasi O (1).

Atau dengan istilah yang lebih ketat,

Ada c yang konstan, sehingga untuk setiap urutan operasi (juga yang berakhir dengan operasi yang mahal) dengan panjang L, waktunya tidak lebih besar dari c * L (Terima kasih Rafał Dowgird )

Mats Fredriksson
sumber
11
"setelah jumlah operasi yang cukup besar" - waktu diamortisasi konstan tidak memerlukan kondisi ini. Ada c yang konstan, sehingga untuk setiap urutan operasi (juga yang berakhir dengan operasi yang mahal) dengan panjang L, waktunya tidak lebih besar dari c * L.
Rafał Dowgird
Dari mana ini mengalokasikan dua kali jumlah yang berasal? Bukankah kita seharusnya mengalokasikan untuk satu entri? Atau itu contoh hipotetis?
talekeDskobeDa
@talekeDskobaDa Ini bukan contoh sewenang-wenang, tetapi algoritma yang banyak digunakan. Jika kami mengalokasikan ruang untuk satu entri pada satu waktu seperti yang Anda sarankan, waktu diamortisasi untuk memasukkan nilai tunggal adalah O (n). Jika kita menggandakan ruang ketika menjadi penuh, waktu diamortisasi jauh lebih baik, O (1). Agar jelas, masalah dengan mengalokasikan ruang untuk satu item pada suatu waktu adalah bahwa array membutuhkan blok besar ruang kontinu. Sangat mudah untuk mendapatkan blok yang lebih besar dari OS tetapi seringkali tidak mungkin untuk memperluas blok yang ada karena mungkin ada beberapa data lain yang disimpan langsung setelahnya.
Artelius
23

Untuk mengembangkan cara berpikir intuitif tentang hal itu, pertimbangkan penyisipan elemen dalam array dinamis (misalnya std::vectordalam C ++). Mari kita plot grafik, yang menunjukkan ketergantungan jumlah operasi (Y) yang diperlukan untuk memasukkan elemen N dalam array:

merencanakan

Bagian vertikal grafik hitam sesuai dengan realokasi memori untuk memperluas array. Di sini kita dapat melihat bahwa ketergantungan ini dapat secara kasar direpresentasikan sebagai garis. Dan persamaan garis ini adalah Y=C*N + b( Ckonstan, b= 0 dalam kasus kami). Karena itu kita dapat mengatakan bahwa kita perlu menghabiskan C*Noperasi rata-rata untuk menambahkan elemen N ke array, atau C*1operasi untuk menambahkan satu elemen (waktu konstan diamortisasi).

Megamozg
sumber
14

Saya menemukan penjelasan Wikipedia di bawah ini bermanfaat, setelah membaca berulang sebanyak 3 kali:

Sumber: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Array Dinamis

Analisis Amortisasi operasi Push untuk Array Dinamis

Pertimbangkan array dinamis yang tumbuh dalam ukuran karena lebih banyak elemen ditambahkan ke dalamnya seperti ArrayList di Jawa. Jika kita mulai dengan array dinamis ukuran 4, akan butuh waktu konstan untuk mendorong empat elemen ke atasnya. Namun, mendorong elemen kelima ke array akan memakan waktu lebih lama karena array harus membuat array baru dengan ukuran ganda saat ini (8), menyalin elemen lama ke array baru, dan kemudian menambahkan elemen baru. Tiga operasi push berikutnya juga akan membutuhkan waktu yang konstan, dan kemudian penambahan berikutnya akan membutuhkan penggandaan ukuran array yang lambat.

Secara umum jika kita mempertimbangkan jumlah sembarang dorongan n ke array ukuran n, kami melihat bahwa operasi dorong membutuhkan waktu yang konstan kecuali untuk yang terakhir yang membutuhkan O (n) waktu untuk melakukan operasi penggandaan ukuran. Karena ada total operasi n kita dapat mengambil rata-rata dari ini dan menemukan bahwa untuk mendorong elemen ke array dinamis membutuhkan: O (n / n) = O (1), waktu konstan. "

Untuk pemahaman saya sebagai cerita sederhana:

Anggaplah Anda memiliki banyak uang. Dan, Anda ingin menumpuknya di sebuah ruangan. Dan, Anda memiliki tangan dan kaki yang panjang, selama yang Anda butuhkan sekarang atau di masa depan. Dan, Anda harus mengisi semua dalam satu ruangan, sehingga mudah untuk menguncinya.

Jadi, Anda langsung ke ujung / sudut ruangan dan mulai menumpuknya. Saat Anda menumpuknya, perlahan ruangan akan kehabisan ruang. Namun, saat Anda mengisinya, mudah untuk menumpuknya. Dapatkan uang, masukkan uang. Mudah. Ini O (1). Kami tidak perlu memindahkan uang sebelumnya.

Begitu ruangan kehabisan ruang. Kami membutuhkan kamar lain, yang lebih besar. Di sini ada masalah, karena kita hanya dapat memiliki 1 kamar sehingga kita hanya memiliki 1 kunci, kita perlu memindahkan semua uang yang ada di ruangan itu ke kamar yang lebih besar. Jadi, pindahkan semua uang, dari kamar kecil, ke kamar yang lebih besar. Artinya, susun semuanya lagi. Jadi, Kita TIDAK perlu memindahkan semua uang sebelumnya. Jadi, itu adalah O (N). (dengan asumsi N adalah jumlah total uang dari uang sebelumnya)

Dengan kata lain, mudah sampai N, hanya 1 operasi, tetapi ketika kita perlu pindah ke ruangan yang lebih besar, kita melakukan operasi N. Jadi, dengan kata lain, jika kita kehabisan rata-rata, itu adalah 1 masukkan di awal, dan 1 lagi bergerak sambil pindah ke ruangan lain. Total 2 operasi, satu insert, satu move.

Dengan asumsi N besar seperti 1 juta bahkan di ruangan kecil, 2 operasi dibandingkan dengan N (1 juta) sebenarnya bukan angka yang sebanding, sehingga dianggap konstan atau O (1).

Dengan asumsi ketika kita melakukan semua hal di atas di ruangan lain yang lebih besar, dan sekali lagi perlu bergerak. Itu masih sama. katakanlah, N2 (katakanlah, 1 miliar) adalah jumlah baru dari jumlah uang di ruang yang lebih besar

Jadi, kami memiliki N2 (yang termasuk N dari sebelumnya karena kami memindahkan semua dari ruang kecil ke ruang lebih besar)

Kami masih membutuhkan hanya 2 operasi, satu dimasukkan ke dalam ruangan yang lebih besar, kemudian operasi pemindahan lainnya untuk pindah ke ruangan yang lebih besar.

Jadi, bahkan untuk N2 (1 miliar), itu adalah 2 operasi untuk masing-masing. yang tidak ada artinya lagi. Jadi, itu konstan, atau O (1)

Jadi, ketika N meningkat dari N ke N2, atau lainnya, itu tidak masalah. Masih konstan, atau operasi O (1) diperlukan untuk masing-masing N.

Sekarang asumsikan, Anda memiliki N sebagai 1, sangat kecil, jumlah uangnya kecil, dan Anda memiliki kamar yang sangat kecil, yang hanya akan memenuhi 1 hitungan uang.

Segera setelah Anda mengisi uang di dalam ruangan, ruangan itu terisi.

Ketika Anda pergi ke ruang yang lebih besar, anggap itu hanya dapat memuat satu uang lagi di dalamnya, total 2 hitungan uang. Itu artinya, uang yang dipindahkan sebelumnya dan 1 lagi. Dan lagi itu diisi.

Dengan cara ini, N tumbuh lambat, dan tidak ada lagi yang konstan O (1), karena kita memindahkan semua uang dari kamar sebelumnya, tetapi hanya dapat memuat 1 lebih banyak uang.

Setelah 100 kali, kamar baru tersebut cocok dengan 100 hitungan uang dari sebelumnya dan 1 lebih banyak uang yang dapat ditampungnya. Ini adalah O (N), karena O (N + 1) adalah O (N), yaitu, tingkat 100 atau 101 sama, keduanya ratusan, berbeda dengan cerita sebelumnya, satu ke jutaan dan satu ke miliaran .

Jadi, ini adalah cara yang tidak efisien dalam mengalokasikan kamar (atau memori / RAM) untuk uang kita (variabel).

Jadi, cara yang baik adalah mengalokasikan lebih banyak ruang, dengan kekuatan 2.

Ukuran kamar 1 = cocok dengan 1 hitungan uang
Ukuran kamar 2 = cocok dengan 4 hitungan uang
Ukuran kamar 3 = cocok dengan 8 jumlah uang
Ukuran kamar 4 = cocok dengan 16 jumlah uang
Ukuran kamar 5 = sesuai dengan 32 jumlah uang
6 ukuran kamar = cocok 64 hitungan uang
Ukuran kamar 7 = cocok 128 hitungan uang
Ukuran kamar 8 = cocok dengan 256 jumlah uang
Ukuran kamar ke-9 = cocok dengan 512 jumlah uang
Ukuran kamar ke-10 = cocok untuk 1024 hitungan uang
Ukuran kamar ke-11 ukuran kamar = cocok dengan jumlah uang pada 2.048
. ..
Ukuran kamar ke-16 = cocok dengan jumlah uang 65.536
...
Ukuran kamar ke-32 = cocok untuk 4.294.967.296 jumlah uang
...
Ukuran kamar ke-64 = cocok untuk jumlah uang ke 18.446.744.073.709.551.616

Kenapa ini lebih baik? Karena terlihat tumbuh lambat di awal, dan lebih cepat nanti, yaitu, dibandingkan dengan jumlah memori dalam RAM kita.

Ini bermanfaat karena, dalam kasus pertama meskipun bagus, jumlah total pekerjaan yang harus dilakukan per uang tetap (2) dan tidak sebanding dengan ukuran kamar (N), ruangan yang kami ambil pada tahap awal mungkin terlalu besar (1 juta) yang tidak dapat kita gunakan sepenuhnya tergantung pada apakah kita dapat memperoleh uang sebanyak itu untuk ditabung sama sekali dalam kasus pertama.

Namun, dalam kasus terakhir, kekuatan 2, ia tumbuh dalam batas RAM kami. Jadi, dengan meningkatkan kekuatan 2, kedua analisis Armotized tetap konstan dan ramah untuk RAM terbatas yang kita miliki saat ini.

Manohar Reddy Poreddy
sumber
2
Ah, jadi O (kasus terburuk / # operasi). Saya suka jawaban ini yang terbaik.
nucleartide
1

Penjelasan di atas berlaku untuk Analisis Agregat, gagasan mengambil "rata-rata" selama beberapa operasi. Saya tidak yakin bagaimana mereka berlaku untuk metode Bankir atau Metode Fisikawan dari Analisis Amortisasi.

Sekarang. Saya tidak yakin dengan jawaban yang benar. Tapi itu harus dilakukan dengan kondisi prinsip dari kedua metode fisikawan + Bankir:

(Jumlah biaya operasi diamortisasi)> = (Jumlah biaya operasi aktual).

Kesulitan utama yang saya hadapi adalah bahwa mengingat biaya operasi amortisasi-asimptotik berbeda dari biaya normal-asimptotik, saya tidak yakin bagaimana menilai signifikansi biaya-biaya diamortisasi.

Itulah ketika seseorang memberi saya biaya yang diamortisasi, saya tahu itu tidak sama dengan biaya normal-asimptotik. Kesimpulan apa yang saya dapat dari biaya-diamortisasi itu?

Karena kami memiliki kasus beberapa operasi ditagih berlebihan sementara operasi lainnya ditagih lebih rendah, satu hipotesis bisa berupa mengutip biaya yang diamortisasi dari operasi individu akan menjadi tidak berarti.

Untuk misalnya: Untuk tumpukan fibonacci, mengutip biaya diamortisasi dari hanya Decreasing-Key menjadi O (1) tidak ada artinya karena biaya dikurangi dengan "pekerjaan yang dilakukan oleh operasi sebelumnya dalam meningkatkan potensi tumpukan".

ATAU

Kita dapat memiliki hipotesis lain yang beralasan tentang biaya perolehan diamortisasi sebagai berikut:

  1. Saya tahu bahwa operasi yang mahal akan didahului oleh beberapa operasi BIAYA RENDAH.

  2. Demi analisis, saya akan menjual terlalu mahal beberapa operasi berbiaya rendah, SEPERTI YANG BIAYA ASYMPTOTIC-BIAYA TIDAK BERUBAH.

  3. Dengan peningkatan operasi berbiaya rendah ini, saya dapat MEMBUKTIKAN OPERASI EKSPENSIF yang memiliki BIAYA ASIMPTOTIK KECIL.

  4. Jadi saya telah meningkatkan / menurunkan ASYMPTOTIC-BOUND dari biaya operasi n.

Jadi analisis biaya-diamortisasi + batas-biaya diamortisasi sekarang hanya berlaku untuk operasi mahal. Operasi yang murah memiliki biaya amortisasi asimptotik yang sama dengan biaya normal asimptotik.

Misraji
sumber
Pikiran yang menarik.
Lonnie Best
0

Kinerja setiap fungsi dapat dirata-ratakan dengan membagi "jumlah total panggilan fungsi" menjadi "total waktu yang diambil untuk semua panggilan yang dilakukan". Bahkan fungsi yang membutuhkan waktu lebih lama dan lebih lama untuk setiap panggilan yang Anda lakukan dapat dirata-ratakan dengan cara ini.

Jadi, esensi dari fungsi yang bekerja Constant Amortized Timeadalah bahwa "waktu rata-rata" ini mencapai langit-langit yang tidak dapat dilampaui karena jumlah panggilan terus meningkat. Setiap panggilan tertentu dapat bervariasi dalam kinerja, tetapi dalam jangka panjang waktu rata-rata ini tidak akan terus tumbuh semakin besar.

Ini adalah kelebihan penting dari sesuatu yang tampil di Constant Amortized Time.

Lonnie Best
sumber