Koszt zamortyzowany

Koszt zamortyzowany – miara złożoności obliczeniowej operacji na strukturze danych. Koszt zamortyzowany operacji jest średnim czasem wykonania przypadającym na jedną operację w pesymistycznym ciągu operacji.

Analiza kosztu zamortyzowanego zajmuje się oszacowaniem czasu niezbędnego do wykonania ciągu operacji, a nie pojedynczej operacji. Może się bowiem zdarzyć, że wykonanie całego ciągu jest mniej kosztowne niż wskazywałaby na to złożoność obliczeniowa jednej operacji, ponieważ tylko niektóre ciągi operacji są możliwe.

Koszt zamortyzowany różni się od kosztu średniego tym, że bierze pod uwagę ciąg operacji i nie jest metodą probabilistyczną. O ile koszt średni reprezentuje wartość oczekiwaną złożoności czasowej operacji, tak koszt zamortyzowany stanowi oszacowany dla pesymistycznego przypadku średniego koszt operacji w ciągu.

Metody analizy kosztu zamortyzowanego

edytuj

Poszczególne metody analizy kosztu zamortyzowanego poniżej będą zilustrowane analizą kosztu operacji na stosie z operacjami Push(x), która wkłada element   na stos, i Multipop(k), która zdejmuje ze stosu   elementów. Niech   oznacza liczbę elementów na stosie. Pesymistyczna złożoność pojedynczej operacji Multipop może być   ponieważ może nastąpić zdjęcie kolejno wszystkich elementów stosu. Analiza kosztu zamortyzowanego posłuży do lepszego oszacowania złożoności tej operacji jako części ciągów operacji na stosie.

Metoda kosztu sumarycznego

edytuj

Jeżeli można oszacować sumaryczny koszt ciągu   operacji na strukturze danych przez funkcję   to mówimy, że zamortyzowany koszt jednej operacji wynosi   W przeciwieństwie do dwóch pozostałych metod, jeżeli w ciągu znajdują się operacje kilku typów, przy tej metodzie zamortyzowany koszt jest przypisywany niezależnie od typu operacji.

Przykład
Ponieważ każdy element włożony na stos może zostać z niego zdjęty co najwyżej raz, liczba operacji zdjęcia elementu ze stosu w ramach Multipop na początkowo pustym stosie nie może przekroczyć liczby operacji Push, która z kolei nie przekracza   Zatem sumaryczny koszt   operacji na stosie jest   a koszt zamortyzowany (przypadający na pojedynczą operację) wynosi  

Metoda księgowania

edytuj

W metodzie księgowania koszt zamortyzowany jednej operacji jest równy sumie jej kosztu faktycznego oraz kredytu, który można przypisać lub odebrać elementom struktury. Operacje, których koszt zamortyzowany przewyższa koszt faktyczny dodają do elementów struktury kredyt, który jest potem wykorzystywany na „opłacenie” operacji, których koszt rzeczywisty jest większy.

Przykład
Każdemu elementowi stosu będziemy przyporządkowywać jeden „kredyt”, który będzie wykorzystywany na opłacenie operacji zdjęcia tego elementu ze stosu. Operacja Push będzie więc miała koszt zamortyzowany 2 (koszt rzeczywisty + jeden kredyt), a operacja Multipop będzie miała koszt zamortyzowany 0 (jej koszt rzeczywisty jest równoważony przez odbierany elementom stosu kredyt). Obie operacje mają więc koszt zamortyzowany  

Metoda potencjału

edytuj

W analizie kosztu zamortyzowanego metodą potencjału przypisujemy strukturze danych w jej stanie po wykonaniu  -tej operacji w ciągu liczbę rzeczywistą   która reprezentuje potencjał struktury danych. Podobnie jak w przypadku kredytu, operacje mogą zwiększać lub zmniejszać potencjał struktury, a sam potencjał może być rozpatrywany jako suma kredytów we wszystkich elementach struktury, z tym, że nie jest on związany z żadnym jej elementem, a z całą strukturą. Koszt zamortyzowany  -tej operacji na strukturze danych określamy następująco:

 

gdzie   jest rzeczywistym jej kosztem. Sumaryczny koszt zamortyzowany ciągu   operacji jest równy

 
Przykład
Definiujemy funkcję potencjału   jako liczbę elementów na stosie. Koszt zamortyzowany operacji Push, wykonanej jako  -ta operacja w ciągu, wynosi
  (potencjał rośnie o 1),
natomiast jeżeli i-tą operacją jest Multipop(k), to jej koszt zamortyzowany wynosi
  gdzie  
ponieważ rzeczywisty koszt operacji wynosi   a jednocześnie potencjał struktury danych spada o  
Obie operacje mają zatem złożoność  

Zobacz też

edytuj

Bibliografia

edytuj
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Diks, K. et al (tłum). Wyd. 8. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 411–420. ISBN 978-83-204-3328-9.