Амортизована анализа
Амортизована анализа у рачунарском смислу представља метод анализе алгоритама који разматра целукупан рад програма. Идеја ове методе говори о томе да, док одређене операције могу бити изузетно скупе, оне не могу често да се појављују како би одговарале за цео програм, јер ће број јефтинијих операција надмашити скупље, дугорочно гледано, враћајући програм преко броја итерација. То је посебно корисно јер се гарантује најгори учинак пре неке претпоставке о стању програма.[1][2]
Историја[уреди | уреди извор]
Амортизована анализа је настала од методе која се зове агрегатна анализа која је сада у склопу амортизоване анализе. Ова техника је први пут званично представљена од стране Роберта Трајана у његовом раду Amortized Computational Complexity(отписане рачурарске конплесности), који истиче потребу за бољом употребом анализе од уобичајне.[2]
Амортизација је првобитно коришћена за специфичну врсту алгоритама, посебно оне које укључују бинарна стабла и операције са сумама. Све у свему, сада је у употреби и долази до изражаја када се анализирају и многи други алгоритми.
Метод[уреди | уреди извор]
Метод захтева познавање оних операција које су могуће. То је најчешће случај са структурама података које имају такву структуру, која остаје непромењена између операција. Основна идеја је да најгора операција може да мења стање на такав начин да се тај најгори случај дуже време не може поново појавити, и на тај начин амортизовати свој трошак, односно своју цену.
Генерално постоје три методе за обављање амортизоване анализе:
- агрегатни метод (the aggregate method)
- метод обрачуна и (the accounting method)
- метод потенцијала (the potential method)
Све ове методе дају исте одговоре, а која ће се користити првенствено зависи од околности и индивидуалних преференција.
- Агрегатна анализа утврђује горњу границу Т(n) укупне цене низа операција, а онда рачуна амортизовани трошак Т(n)/n.
- Метод обрачуна одређује појединачан трошак сваке операције, комбинујући време хитно извршених операција са временом будућих извршених операција. Обично, многе краткотрајне операције акумулирају "дуг" неповољног стања у малим корацима, док ретке дуготрајне операције драстично смањују "дуг“.
- Метод потенцијала је сличан методи обрачуна, само што нагомилава операције, како би компезовао недостатак истих.
Употреба[уреди | уреди извор]
- Ова анализа је показала добре резултате у општој употреби
Референце[уреди | уреди извор]
- ^ „Lecture 7: Amortized Analysis” (PDF). www.cs.cmu.edu. Приступљено 14. 3. 2015.
- ^ а б Fiebrink, Rebecca (2007), Amortized Analysis Explained (PDF), Архивирано из оригинала (PDF) 20. 10. 2013. г., Приступљено 03. 05. 2011
Спољашње везе[уреди | уреди извор]
- Обрачун и анализе конкуренције Архивирано на сајту Wayback Machine (5. октобар 2006)
- Амортизована Анализа Објашњење