Амортизована анализа

Из Википедије, слободне енциклопедије

Амортизована анализа у рачунарском смислу представља метод анализе алгоритама који разматра целукупан рад програма. Идеја ове методе говори о томе да, док одређене операције могу бити изузетно скупе, оне не могу често да се појављују како би одговарале за цео програм, јер ће број јефтинијих операција надмашити скупље, дугорочно гледано, враћајући програм преко броја итерација. То је посебно корисно јер се гарантује најгори учинак пре неке претпоставке о стању програма.

Историја[уреди]

Амортизована анализа је настала од методе која се зове агрегатна анализа која је сада у склопу амортизоване анализе. Ова техника је први пут званично представљена од стране Роберта Трајанау његовом раду Amortized Computational Complexity(отписане рачурарске конплесности), који истиче потребу за бољом употребом анализе од уобичајне.

Амортизација је првобитно коришћена за специфичну врсту алгоритама, посебно оне које укључују бинарна стабла и операције са сумама. Све у свему, сада је у употреби и долази до изражаја када се анализирају и многи други алгоритми.

Метод[уреди]

Метод захтева познавање оних операција које су могуће. То је најчешће случај са структурама података које имају такву структуру, која остаје непромењена између операција. Основна идеја је да најгора операција може да мења стање на такав начин да се тај најгори случај дуже време не може поново појавити, и на тај начин амортизовати свој трошак, односно своју цену.

Генерално постоје три методе за обављање амортизоване анализе:

  • агрегатни метод (the aggregate method)
  • метод обрачуна и (the accounting method)
  • метод потенцијала (the potential method)

Све ове методе дају исте одговоре, а која ће се користити првенствено зависи од околности и индивидуалних преференција.

  • Агрегатна анализа утврђује горњу границу Т(n) укупне цене низа операција, а онда рачуна амортизовани трошак Т(n)/n.
  • Метод обрачуна одређује појединачан трошак сваке операције, комбинујући време хитно извршених операција са временом будућих извршених операција. Обично, многе краткотрајне операције акумулирају "дуг" неповољног стања у малим корацима, док ретке дуготрајне операције драстично смањују "дуг“.
  • Метод потенцијала је сличан методи обрачуна, само што нагомилава операције, како би компезовао недостатак истих.

Употреба[уреди]

  • Ова анализа је показала добре резултате у општој употреби

Спољашње везе[уреди]