Nuolatinis amortizuotas laikas

Ką reiškia „Nuolatinis amortizuotas laikas“, kai kalbama apie algoritmo sudėtingumą?

352
14 окт. nustatė VarunGupta 14 okt. 2008-10-14 11:32 '08 at 11:32 2008-10-14 11:32
@ 5 atsakymai

Amortizuotas laikas paaiškinamas paprastais žodžiais:

Jei atliksite operaciją, pvz., Milijoną kartų, nerūpi blogiausiu atveju, o geriausiu atveju - ši operacija - kas jums rūpi - kiek laiko jums reikia pakartoti milijoną kartų.

Taigi nesvarbu, ar operacija bus labai lėta, o kartais „retai“ yra pakankamai reta, kad būtų galima susilpninti. Iš esmės amortizuotas laikas reiškia „vidutinį laiką, praleistą operacijai, jei atliekate daugybę operacijų“. Amortizuotas laikas neturi būti pastovus; Galite turėti linijinį ir logaritminį amortizuotą laiką arba kažką kitą.

Paimkite dinamiško masyvo kilimėlių pavyzdį, į kurį vėl įtraukiate naujus elementus. Paprastai elementas pridedamas pastoviu laiku (t.y. O(1) ). Bet kiekvieną kartą, kai masyvas yra pilnas, jūs skiriate du kartus daugiau vietos, kopijuojate duomenis į naują regioną ir atlaisvinkite seną erdvę. Darant prielaidą, kad paskirstymai ir laisvosios atliekos vykdomos pastoviu laiku, šis išplėtimo procesas užima O(n) laiką, kur n yra dabartinis masyvo dydis.

Taigi, kiekvieną kartą, kai padidinate, užtrunka apie du kartus daugiau laiko nei paskutinė. Bet jūs taip pat laukėte du kartus prieš tai! Taigi, kiekvieno plėtinio kaina gali būti „paskirstyta“ tarp intarpų. Tai reiškia, kad ilgainiui bendras laikas, praleistas pridedant m elementus masyvui, yra O(m) , todėl amortizuotas laikas (t. Y. Laikas įterpti) yra O(1) .

681
30 окт. atsakymą pateikė Artelius 30 d. 2008-10-30 12:48 '08, 12:48 2008-10-30 12:48

Tai reiškia, kad laikui bėgant blogiausias atvejis bus numatytas O (1) arba laiko konstanta. Dažnas pavyzdys yra dinamiška masyvas. Jei jau priskyrome atmintį naujam įrašui, pridėkite jį kaip O (1). Jei to nepadarėme, tai padarysime pabrėždami, pvz., Dabartinę sumą du kartus. Šis konkretus įrašas nebus O (1), o kažkas kitas.

Svarbu, kad algoritmas užtikrintų, kad po operacijų sekos brangiai kainuoja operacijos, todėl visa operacija O (1) bus perduota.

Arba griežtesnėmis sąlygomis.

Yra konstanta c, kad kiekvienai operacijų sekai (kuri taip pat baigiasi brangia operacija) ilgis yra L, laikas yra ne ilgesnis kaip c * L (dėka Rafał Dowgird )

51
14 окт. Mats Fredriksson atsakymas spalio 14 d 2008-10-14 11:48 '08 at 11:48 2008-10-14 11:48

Norėdami sukurti intuityvų mąstymo būdą, apsvarstykite galimybę įtraukti elementus į dinaminę masyvą (pvz., std::vector C ++). Sukurkite grafiką, rodantį operacijų (Y), reikalingų N elementams įterpti į masyvą, skaičių:

2019

19 янв. atsakymą pateikė Megamozg 19 d. 2017-01-19 13:17 '17, 17:17 pm 2017-01-19 13:17

Po pakartotinio svarstymo 3 kartus rado tokį Wikipedijos aprašymą:

Šaltinis: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

„Dinaminis masyvas

Dinaminės struktūros amortizuota stūmimo operacijos analizė

Apsvarstykite dinamišką masyvą, kurio dydis auga, nes prie jo pridedama daugiau elementų, pvz., „ArrayList“ „Java“. Jei pradėtume naudoti 4 dydžio dinaminę masyvą, keturių elementų įtraukimas į jį būtų pastovus. Tačiau, paspaudus penktą elementą šiame masyve, reikia daugiau laiko, nes masyvas turėtų sukurti naują masyvą su dvigubu dabartiniu dydžiu (8), kopijuoti senus elementus į naują masyvą ir tada pridėti naują elementą. Kitos trys stūmimo operacijos taip pat imsis laiko konstantų, o paskui reikės kito lėto dvigubo masyvo dydžio.

Apskritai, jei mes svarstome savavališką skaičių paspaudimų n ant n dydžio dydžio masyvo, pastebime, kad stūmimo operacijos imasi pastovaus laiko, išskyrus pastarąjį, kuriam reikia laiko O (n) atlikti dvigubo dydžio operaciją. Kadangi buvo tik n operacijos, mes galime užtrukti viduryje ir surasti tai, ko reikia norint stumti elementus į dinaminę masyvą: O (n / n) = O (1), pastovus laikas. "

Mano supratimui, kaip paprasta istorija:

Tarkime, kad turite daug pinigų. Ir jūs norite įdėti juos į kambarį. Ir jūs turite ilgas rankas ir kojas, kiek jums reikia dabar ar ateityje. Ir jūs turite užpildyti viską viename kambaryje, todėl jį lengva užblokuoti.

Taigi, einate tiesiai į kambario kampą ir pradėkite juos sukrauti. Įdėję juos, lėtai kambaryje nebus pakankamai vietos. Tačiau, kai užpildote, jie buvo lengvai pakuojami. Turite pinigų, įdėkite pinigų. Lengva Tai yra O (1). Mums nereikia perkelti ankstesnių pinigų.

Kai patalpa išdžiūsta. Mums reikia dar didesnio kambario. Čia yra problema, nes mes galime turėti tik 1 kambarį, todėl mes galime turėti tik 1 užraktą, mes turime perkelti visus esamus pinigus į šį didelį kambarį. Taigi perkelkite visus pinigus iš mažo kambario į didelį kambarį. Tai reiškia, kad juos vėl sugrupuokite. Taigi, turime perkelti visus ankstesnius pinigus. Taigi, tai yra O (N). (darant prielaidą, kad N yra bendra pinigų suma už ankstesnius pinigus)

Kitaip tariant, tai buvo lengva N, tik 1 operacija, bet kai mums reikia perkelti į didelį kambarį, atlikome N operacijas. Kitaip tariant, jei mes vidutiniškai, tai yra 1 įdėklas pradžioje ir dar 1 judėjimas, kai persikelia į kitą kambarį. Tik 2 operacijos, vienas įdėklas, vienas judėjimas.

Darant prielaidą, kad N yra didelis, kaip 1 milijonas net mažame kambaryje, 2 operacijos, palyginti su N (1 mln.), Iš tikrųjų nėra palyginamos, todėl jis laikomas nuolatiniu arba O (1).

Darant prielaidą, kad darome visą aukščiau esantį aukštą kambarį ir vėl turime judėti. Tai vienodai. Tarkime, N2 (tarkim, 1 mlrd.) yra nauja pinigų suma didesniame kambaryje

Taigi, mes turime N2 (į kurį įeina N ankstesnis, nes viskas perkeliama iš mažo į didesnį kambarį)

Mums vis dar reikia tik 2 operacijų, vieno įterpimo į didelį kambarį, tada kitą judėjimo operaciją, norėdami pereiti į dar didesnį kambarį.

Taigi, net ir N2 (1 mlrd.), Kiekvienam iš jų yra 2 operacijos. tai nieko daugiau. Todėl jis yra pastovus arba O (1)

Taigi, kadangi N padidėja nuo N iki N2 ar kito, tai nesvarbu. Jis vis dar yra pastovus, arba O (1) operacijos, reikalingos kiekvienam N.


Tarkime, kad jūs turite N kaip 1, jis yra labai mažas, pinigų suma yra maža, ir jūs turite labai mažą kambarį, kuris atitiks tik 1 pinigų sumą.

Kai tik užpildysite pinigus kambaryje, kambarys yra pilnas.

Kai einate į didelį kambarį, darykite prielaidą, kad ji gali turėti tik dar vieną sumą, tik 2 sąskaitas. Tai reiškia, kad ankstesni pinigai persikėlė ir dar 1. Ir vėl ji yra pilna.

Taigi, N auga lėtai, o tai nėra daugiau pastovus O (1), nes mes perkeliame visą pinigus iš ankstesnio kambario, bet mes galime tik tilpti dar vieną dieną.

Po 100 kartų naujame kambaryje yra 100 vienetų pinigų iš ankstesnių ir 1 daugiau pinigų, kuriuos jis gali talpinti. Tai yra O (N), nes O (N + 1) - O (N), ty 100 arba 101 galia yra vienoda, tiek šimtai - priešingai nei ankstesnė istorija - nuo milijonų iki milijardų.

Taigi, tai yra neefektyvus būdas paskirstyti kambarius (arba atmintį / RAM) mūsų pinigams (kintamiesiems).


Taigi, geras būdas yra suteikti daugiau erdvės su įgaliojimais.

1-ojo kambario dydis = viena piniginė sąskaita
2-ojo kambario dydis = 4 piniginės sąskaitos
3-ojo kambario dydis = 8 pinigų
4. kambario dydis = 16 gramų pinigų
5-ojo kambario dydis = 32 pinigų sąskaitos
6-ojo kambario dydis = 64 piniginės sąskaitos
7. kambario dydis = 128 gramai pinigų
8. kambario dydis = 256 pinigų sąskaitos
9-ojo kambario dydis = 512 pinigų
10-ojo kambario dydis = tinkamas 1024 pinigų sumai 11-ojo kambario dydis = atitinka 2048 pinigų sumas
...
16-ojo kambario dydis = 65 536 pinigų rungtynės - ...
32-ojo kambario dydis = 4,294,967,296 mln. Dolerių

...
64-ojo kambario dydis = tinka 18,446,744,073,709,551,616 pinigų sumai

Kodėl tai geriau? Kadangi jis pradeda augti lėtai pradžioje ir greičiau, tai yra, palyginti su atminties kiekiu mūsų atmintyje.

Tai naudinga, nes pirmuoju atveju, nors ir gerai, bendras darbo užmokestis, kurį reikia atlikti už pinigus, yra fiksuotas (2) ir nėra panašus į kambario dydį (N), o pradiniame etape priimtas kambarys gali būti per didelis. (1 mln.), Kurių mes negalime visiškai panaudoti, priklausomai nuo to, ar galime gauti tiek daug pinigų, kad sutaupytume pirmąjį atvejį.

Tačiau pastaruoju atveju, 2 laipsnis, jis auga mūsų atmintyje. Taigi, didėjant 2 laipsniui, Armotized analizė išlieka pastovi, ir ji yra draugiška ribotai RAM, kurią turime šiandien.

7
08 июля '16 в 10:42 2016-07-08 10:42 atsakymą pateikė Manohar Reddy Poreddy liepos 8 d., 16 d., 10:42 2016-07-08 10:42

Pirmiau pateikti paaiškinimai yra susiję su apibendrinta analize, idėja priimti „vidurkį“ kelioms operacijoms. Nesu tikras, kaip jie susiję su bankininkų metodu ar su juo susijusių fizikų analizės metodais.

Dabar Nesu visiškai tikras dėl teisingo atsakymo. Tačiau taip yra dėl abiejų metodų „Fizika + bankininkas“ esminės sąlygos:

(Amortizuotos savikainos suma)> = (faktinių operacijų išlaidų suma).

Pagrindiniai sunkumai, su kuriais susiduriu, yra tai, kad, atsižvelgiant į tai, kad dėl amortizacijos ir asimptotinių operacijų sąnaudos skiriasi nuo įprastinių asimptotinių kaštų, nesu įsitikinęs, kaip įvertinti nuvertėjusių sąnaudų reikšmę.

Tai reiškia, kad kai kas man suteikia nuvertėjusią vertę, žinau, kad tai nėra tokia pati kaip normalios asimptotinės vertės. Kokias išvadas galiu daryti iš amortizuotos savikainos?

Kadangi susiduriame su kai kurių operacijų perkrovimu, o kitos operacijos yra papildomos, viena hipotezė gali būti ta, kad atskirų operacijų nusidėvėjimo sąnaudų citavimas būtų beprasmis.

Pavyzdžiui, kai Fibonacci cupping, apskaičiuodama amortizuotos savikainos, kuri paprasčiausiai sumažina raktą O (1), vertė yra beprasmė, nes išlaidos sumažinamos „ankstesnių operacijų atliktu darbu, didinant krūvos potencialą“.

Or

Galėtume turėti kitą hipotezę, kad amortizuotos savikainos priežastys yra tokios:

  • Žinau, kad prieš brangias operacijas bus atliekamos operacijos MULTIPLE LOW-COST.

  • Analizei atliksiu keletą pigių operacijų, kad jų asimptotinė kaina nepasikeistų.

  • Dėl šių padidėjusių pigių operacijų galiu užtikrinti, kad brangi operacinė sistema turi SCALING RACK.

  • Taigi, aš pagerinčiau / sumažinau n operacijų kaštus.

Taigi amortizuotos savikainos + nusidėvėjimo sąnaudų analizė dabar taikoma tik brangiems sandoriams. Pigios operacijos turi tokias pačias asimptotines nusidėvėjimo sąnaudas, kaip ir jų įprastos asimptotinės išlaidos.

1
10 мая '13 в 23:38 2013-05-10 23:38 atsakymą pateikė „ Misraji “ gegužės 13 d. 23:38 2013-05-10 23:38

Kiti klausimai apie arba Užduoti klausimą etiketes