Potential Methode für die amortisierte Analyse.

André Schulz, WWU Münster
Notizen zur Vorlesung, Datenstrukturen für Fortgeschrittene WS10
Potential Methode für die amortisierte Analyse.
Amortisierte Kosten. Wenn wir von amortisierten Kosten sprechen, meinen wir
die die durchschnittlichen Kosten einer Operation in einer Sequenz von Operationen.
Zum Beispiel kann das Entfernen des Minimums eines Heaps teuer sein, aber nur dann
wenn vorher viele Einträge in den Heap eingefügt wurden. In dieser Situation ist es
möglich, die Kosten des Entfernens auf die vorigen Einfüge-operationen umzulegen.
Die worst case Kosten des Entfernens sind nach wie vor hoch, doch die amortisierten
Kosten können deutlich geringer ausfallen.
Potential einer Datenstruktur. Wir betrachten eine Menge von Operationen, deren amortisierte Kosten wir abschätzen wollen. Dabei überführt die ite Operation die
Datenstruktur Di−1 in die Datenstruktur Di . Für jede Datenstruktur definieren wir ein
Potential mittels einer Funktion Φ : {Di } → R. Der Einfachheit halber fordern wir:
Φ(D0 ) = 0,
Φ(Di ) ≥ 0
(1)
für alle i ≥ 0.
(2)
Amortisierung über das Potential. Die realen Kosten der iten Operation bezeichnen wir mit ci . Die amortisierten Kosten, die wir bestimmen wollen, nennen wir
ĉi . Es hängt von der Wahl der Potentialfunktion Φ ab, wie hoch diese Kosten sind. Für
dieselbe Datenstruktur mit den selben Operationen kann eine andere Potentialfunktion
andere amortisierte Kosten implizieren. Deshalb sind die Kosten ĉi immer in Bezug zu
Φ zu sehen, auch wenn wir das nicht immer extra erwähnen. Die amortisierten Kosten
setzen sich aus den tatsächlichen Kosten und der Potentialdifferenz (vor und nach der
Ausführung von Operation i) zusammen. Demnach ist
ĉi := ci + Φ(Di ) − Φ(Di−1 ).
(3)
Wenn die Potentialdifferenz positiv ist, haben wir bei der Ausführung der iten Operation etwas vorausbezahlt. Eine Operation die das Potential verringert, bedient sich von
diesen vorausbezahlten Kosten. Die Annahmen (1) und (2) garantieren, dass nie eine
Operation Kosten beansprucht, die noch nicht eingezahlt wurden.
Um die Definition der amortisierten Kosten zu rechtfertigen sehen wir uns die Sum-
1
me der amortisieren Kosten unserer Sequenz an. Es gilt
n
X
ĉi =
i=1
=
n
X
ci
i=1
n
X
+ (Φ(Di+1 ) − Φ(Di ))
(Definition (3))
!
ci
+ Φ(Dn ) − Φ(D0 )
(Teleskopsumme)
i=1
≥
n
X
ci .
(wegen (1) und (2))
i=1
Demnach ist die Summe der amortisierten Kosten eine obere Schranke für die Summe
der tatsächlichen Kosten – und das ist genau das, was wir wollen.
Ein Beispiel: Binärzähler. Wir wollen einen Binärzahler simulieren. Die Ziffern des
Zählers stehen in einem Array A. Das Beispiel mag konstruiert aussehen, es wird uns
Algorithm 1 Increment
1: A[0] ← A[0] + 1
2: i ← 0
3: while A[i] = 2 do
4:
A[i + 1] ← A[i + 1] + 1
5:
A[i] ← 0
6:
i←i+1
7: end while
aber im Vorlauf der Vorlesung noch als reales Problem”begegnen. Der Aufwand von
”
Increment hängt vom Stand des Zählers ab. Sei Ai das Array A nach dem iten Aufruf
von Increment. Wir müssen die Schleife zwischen Zeile 3 und 7 so oft durchlaufen, bis
in A[i] keine 2 steht. Dies ist genau die Stelle, wir nennen sie k, an der in Ai−1 die erste
0 stand. Wir können die Kosten so skalieren, dass
ci ≤ k.
Im worst case ist der Aufwand demnach O(log n).
Wir widmen uns nun der amortisierten Kosten, die durch folgende Potentialfunktion
impliziert werden. Wir definieren
Φ(Ai ) := Anzahl der 1en in Ai .
Unsere Wahl erfüllt offensichtlich die Annahmen (1) und (2). Wenn beim Aufruf von
Increment die erste 0 an der Stelle k auftritt, werden von Increment die davor liegenden 1en auf 0 gesetzt und A[i] von 0 auf 1. Im Beispiel:
0101101111
0101110000.
2
wird zu
Also haben wir
Φ(Ai ) − Φ(Ai−1 ) = −k + 2.
Und demnach sind die amortisierten Kosten
ĉi ≤k − k + 2 = 2.
Fibonacci Heaps. An dieser Stelle gehen wir noch einmal kurz darauf ein, wieso als
Potentialfunktion bei den Fibonacci Heaps die Funktion
Φ(F ) = |W | + 2m
gewählt wurde. Zur Erinnerung: W war die Wurzelliste und m sie Anzahl der markierten Knoten. Es gab zwei aufwendige Operationen bei den Fibonacci Heaps:
(1) ExtractMin. Hier war vor allem der Aufruf von Repair teuer. Dieser kostete
O(|W |). Dafür wurde aber auch die Wurzelliste verkürzt (von |W | auf maximal
D(n)). Um diese Kosten abrechnen zu können, taucht in Φ das |W | auf.
(2) DecreaseKey. Hier entstand der Aufwand durch den wiederholten Aufruf von
CascadeCut. Jeder dieser Aufrufe entfernt jedoch auch eine Markierung, deshalb enthält die Potentialfunktion das m. Da jedes CascadeCut jedoch auch die
Wurzelliste um einen Eintrag erweitert, ist es nötig, die Anzahl der Marken mit
Faktor 2 in Φ aufzunehmen.
3