Poistoanalyysi

Kuoletusanalyysi on menetelmä algoritmin laskennallisen monimutkaisuuden analysoimiseksi , jota käytetään tapauksissa, joissa algoritmin yhden vaiheen suoritusaika kerrottuna vaiheiden määrällä antaa liian suuren arvion koko algoritmin suoritusajasta verrattuna mitä se todella on [1] .

Historia

Robert Tarjan otti termin käyttöön vuonna 1985 [2] . Aluksi amortisoitua analyysiä käytettiin vain rajoitetulle joukolle algoritmeja, jotka työskentelivät binääripuiden tai liittooperaatioiden kanssa , mutta tähän mennessä menetelmä on yleistynyt ja sitä käytetään monien muuntyyppisten algoritmien analysoinnissa [3] .

Menetelmä

Kuoletusanalyysin pääajatuksena on, että mikä tahansa työvoimavaltainen toimenpide muuttaa ohjelman tilaa siten, että ennen seuraavaa työvoimavaltaista toimenpidettä melko paljon pieniä menee välttämättä ohi, mikä "amortioi" panoksen. työvaltaisesta toiminnasta. Kuoletetun analyysin suorittamiseen on kolme päämenetelmää: aggregaatioanalyysi, ennakkomaksumenetelmä ja potentiaalinen menetelmä. Kaikki kolme antavat oikean vastauksen ja tietyssä tapauksessa valitaan yleensä sopivin [4] :

Aggregointianalyysissä toimintojen suoritusajalle lasketaan ylempi estimaatti , jolloin yhden operaation kuoletuksen monimutkaisuus rinnastetaan [4] . $T(n)$ $n$ ${\textstyle T(n)/n}$
Ennakkomaksumenetelmässä jokaiselle tapahtumalle on ennalta määritetty jaksotettu hankintameno joka voi poiketa sen todellisesta hankintamenosta. Samaan aikaan "halvempien" transaktioiden jaksotettu hankintameno on yleensä korkeampi kuin todellisen, ja "kallimpien" jaksotettu hankintameno on pienempi kuin todellinen. Tästä johtuen halpoja liiketoimia toteutettaessa kertyy summa, joka voidaan "käyttää" sellaisen tapahtuman toteuttamiseen, jonka jaksotettu hankintameno on pienempi kuin todellinen. Oletetaan, että alkusumma on nolla, ja jos se ei muutu negatiiviseksi algoritmin aikana, niin algoritmin kokonaisajoaika on yhtä suuri kuin toimintojen jaksotetun kokonaiskustannusten ja kertyneen summan erotus. Siten transaktioiden jaksotettu hankintameno on todellisen hankintamenon ylempi arvio edellyttäen, että kertyneestä määrästä ei tule negatiivista [4] .
Potentiaalien menetelmässä kumuloituva summa lasketaan tietorakenteen tilan funktiona ("potentiaali"). Jaksotettu hankintameno on tässä tapauksessa yhtä suuri kuin todellisten kustannusten ja potentiaalin muutoksen summa [4] .

Esimerkkejä

Dynaaminen matriisi

Dynaamisessa taulukossa on indeksoinnin lisäksi push -toiminto , joka lisää elementin taulukon loppuun ja lisää sen kokoa yhdellä. Java- ja C++-säilötArrayList ovat esimerkkejästd::vector tällaisesta taulukosta . Jos taulukon koko on aluksi 4, siihen voidaan lisätä 4 elementtiä ja jokainen lisäys vie vakioajan. Viidennen elementin lisääminen edellyttää uuden 8-koon taulukon luomista, johon siirretään vanhan elementit ja sitten lisätään uusi elementti. Seuraavat kolme push- operaatiota vievät jälleen vakioajan, jonka jälkeen taulukko on jälleen tuplattava.

Yleisesti ottaen, jos push- operaatioita suoritettiin kooltaan , kaikki nämä toiminnot suoritetaan vakioajassa, paitsi viimeinen, joka kestää . Tästä voimme päätellä, että elementin lisäämisen jaksotettu kustannus dynaamiseen taulukkoon on [4] . $n+1$ $n$ $\Theta(n)$ ${\textstyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$

Muistiinpanot

Allan Borodinja Ran El-Yaniv. Online-laskenta ja kilpailullinen analyysi (englanniksi) . - Cambridge University Press , 1998. - s. 20 141.

↑ Luento 7: Amortized Analysis . Carnegie Mellonin yliopisto . Haettu 14. maaliskuuta 2015. Arkistoitu alkuperäisestä 26. helmikuuta 2015. (määrätön)
↑ Tarjan, Robert Endre . Amortized Computational Complexity // SIAM Journal on Algebraic and Discrete Methods : päiväkirja. - 1985. - huhtikuu ( osa 6 , nro 2 ) . - s. 306-318 . - doi : 10.1137/0606031 .
↑ Rebecca Fiebrink (2007), Amortized Analysis Explained , < http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf > . Haettu 3. toukokuuta 2011. Arkistoitu 20. lokakuuta 2013 Wayback Machinessa
↑ 1 2 3 4 5 Kozen, Dexter CS 3110 Luento 20: Amortized Analysis . Cornellin yliopisto (kevät 2011). Haettu 14. maaliskuuta 2015. Arkistoitu alkuperäisestä 3. lokakuuta 2018. (määrätön)