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

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 $x$ na stos, i Multipop(k), która zdejmuje ze stosu $k$ elementów. Niech $m$ oznacza liczbę elementów na stosie. Pesymistyczna złożoność pojedynczej operacji Multipop może być ${\mathcal {O}}(m),$ 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

Jeżeli można oszacować sumaryczny koszt ciągu $n$ operacji na strukturze danych przez funkcję $T(n),$ to mówimy, że zamortyzowany koszt jednej operacji wynosi ${\frac {T(n)}{n}}.$ 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

n.

Zatem sumaryczny koszt

n

operacji na stosie jest

{\mathcal {O}}(n),

a koszt zamortyzowany (przypadający na pojedynczą operację) wynosi

{\frac {{\mathcal {O}}(n)}{n}}={\mathcal {O}}(1).

Metoda księgowania

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

{\mathcal {O}}(1).

Metoda potencjału

W analizie kosztu zamortyzowanego metodą potencjału przypisujemy strukturze danych w jej stanie po wykonaniu $i$ -tej operacji w ciągu liczbę rzeczywistą $\Phi _{i},$ 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 $i$ -tej operacji na strukturze danych określamy następująco:

{\widehat {c_{i}}}=c_{i}+\Phi _{i}-\Phi _{i-1},

gdzie $c_{i}$ jest rzeczywistym jej kosztem. Sumaryczny koszt zamortyzowany ciągu $n$ operacji jest równy

\sum _{i=1}^{n}{\widehat {c_{i}}}=\sum _{i=1}^{n}c_{i}+\Phi _{n}-\Phi _{0}.

Przykład

Definiujemy funkcję potencjału

\Phi

jako liczbę elementów na stosie. Koszt zamortyzowany operacji Push, wykonanej jako

i

-ta operacja w ciągu, wynosi

{\widehat {c_{i}}}=c_{i}+\Phi _{i}-\Phi _{i-1}=1+1=2

(potencjał rośnie o 1),

natomiast jeżeli i-tą operacją jest Multipop(k), to jej koszt zamortyzowany wynosi

{\widehat {c_{i}}}=c_{i}+\Phi _{i}-\Phi _{i-1}=k'-k'=0,

gdzie

k'=\min(k,m)

ponieważ rzeczywisty koszt operacji wynosi

k',

a jednocześnie potencjał struktury danych spada o

k'.

Obie operacje mają zatem złożoność

{\mathcal {O}}(1).

Zobacz też

Bibliografia

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.