Metoda potencjału 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ż struktura danych złożoność obliczeniowa
Bibliografia
Kategoria:Teoria obliczeń Kategoria:Algorytmika