Koszt zamortyzowany
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: czym się właściwie różni koszt od złożoności? Brak definicji formalej. Przydałby się jakiś przykład, obecnie treść artykułu jest niezrozumiała.. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Koszt zamortyzowany – w informatyce jedna z miar złożoności obliczeniowej operacji na strukturze danych.
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 oszacowane dla pesymistycznego przypadku średniego kosztu operacji w ciągu.
Spis treści |
[edytuj] Metody analizy kosztu zamortyzowanego
[edytuj] 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 
. 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,
[edytuj] 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.
[edytuj] 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ą Φ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:
,
gdzie ci jest rzeczywistym jej kosztem. Sumaryczny koszt zamortyzowany ciągu n operacji jest równy
.
[edytuj] 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: Wydawnictwo Naukowo-Techniczne, 2007, ss. 411–420. ISBN 978-83-204-3328-9.
