Amortisierte Analyse
Autor: Pascal LenznerBei vielen Algorithmen treten Folgen von Operationen auf Datenstrukturen, wie
zum Beispiel Stacks, Queues oder Heaps, auf. Um solche Algorithmen zu analysieren, müssen wir die Kosten abschätzen, die eine solche Folge von \(n\) Operationen im Worstcase benötigt.
Oftmals kennen wir dabei die Worstcase-Kosten jeder einzelnen
Operation und somit könnten wir diese Kosten einfach über alle \(n\) Operationen aufsummieren. Dies führt tatsächlich zu einer oberen Schranke für die Gesamtkosten der Operationenfolge, allerdings ist eine solche Abschätzung in vielen Fällen zu
pessimistisch.
Amortisierte Analyse ist eine Technik, die es ermöglicht, die Worstcase-Kosten von Operationenfolgen viel genauer abzuschätzen.
Amortisierte Analyse liefert meist dann eine viel genauere Analyse, wenn nicht alle Operationen in der Operationenfolge gleich teuer sind, sondern die Kosten einer einzelnen Operation vom aktuellen Zustand der Datenstruktur und somit von den vorangegangenen anderen Operationen abhängen. Beispielsweise kann es passieren, dass eine teure Operation nur dann auftritt, wenn vorher viele billige Operationen aufgetreten sind.
Es gibt im Wesentlichen drei verschiedene Vorgehensweisen bei der
amortisierten Analyse: die Aggregatmethode, die Guthabenmethode
und die Potentialmethode. Diese werden im Folgenden am Beispiel des Inkrementierens eines Binärzählers vorgestellt.
Anwendungsbeispiel: Inkrementieren eines Binärzählers
Wir betrachten einen \(k\)-Bit-Binärzähler. Dieser besteht aus einem
Array von \(k\)-Bits \(b_0, \ldots, b_{k-1}\), welches die Zahl \(x= \sum_{i=0}^{k-1}
2^i b_i\) codiert. Dabei ist anfangs \(x=0\).
Der Binärzähler hat genau eine
Operation namens increment, die \(x\) um \(1\) erhöht (modulo \(2^k\)) und das Bitarray entsprechend modifiziert. Die Kosten einer increment-Operation seien dabei die
Anzahl der dafür benötigten Bitänderungen. Hier ein Beispiel:
Die Operation increment angewendet auf \(x=3\) kostet somit genau \(3\), da sich der Wert an den drei Bitpositionen \(b_0, b_1\) und \(b_2\) ändert.
Es ist leicht zu sehen, dass die teuerste increment-Operation insbesondere dann auftritt, wenn vorher alle \(k\) Bits den Wert \(1\) hatten. In diesem Fall kostet increment dann genau \(k\), da alle Bits geflippt werden.
Wir haben hier also ein Beispiel dafür, dass die Kosten für eine Operation nicht konstant sind, sondern stark vom Zustand der Datenstruktur (in unserem Fall das Bit-Array) abhängen.
Traditionelle Worstcase-Analyse
Wir wollen die Worstcase-Kosten von \(n\) increment-Operationen, gestartet auf einem \(k\)-Bit-Zähler mit Anfangswert \(x=0\), abschätzen. Diese Kosten nennen wir \(T(n)\). Wir haben eben gesehen, dass eine einzelne increment-Operation im schlimmsten Fall Kosten von \(k\) Bitflips haben kann. Da wir \(n\)-mal inkrementieren, ist somit \[T(n) \leq n\cdot k \in \mathcal{O}(kn)\] eine korrekte obere Schranke für die Kosten der Operationenfolge.
Wir werden nun zeigen, dass diese Schranke extrem pessimistisch und sehr weit von den tatsächlich auftretenden Kosten entfernt ist. Der Grund liegt darin, dass es nur sehr selten vorkommt, dass increment tatsächlich \(k\) viele Bitflips verursacht.
Die Aggregatmethode
Die Grundidee bei der Aggregatmethode ist folgende: Angenommen wir wüssten, dass
eine Sequenz von \(n\) Operationen Zeit \(T(n)\) kostet, dann sind die
durchschnittlichen Kosten pro Operation \(T(n)/n\). Unser Ziel ist es also, \(T(n)\) möglichst genau zu berechnen, ohne jedes Mal den Worstcase für jede Operation anzunehmen. Dafür summieren wir die tatsächlich anfallenden Kosten der einzelnen Operationen möglichst genau auf.
Betrachten wir, was passiert, wenn wir für \(k=5\) ein paarmal die increment-Operation anwenden:
Wir sehen, dass der Worstcase von \(5\) Bitflips in den ersten \(15\) increment-Operationen überhaupt nicht auftritt. Erst beim \(16.\) Mal increment (beim Schritt \(01111 \to 10000\)) entstehen so hohe Kosten. Außerdem sehen wir auch, dass jede zweite increment-Operation minimale Kosten von nur einem Bitflip hat!
Es ist leicht zu sehen, dass sich nicht jedes Bit bei jedem increment ändert. Genauer gilt sogar Folgendes: Bit \(b_0\) ändert sich in jeder Operation, Bit \(b_1\) alle \(2\) Operationen,
Bit \(b_2\) alle \(4\) Operationen usw. Allgemein gilt, dass sich Bit \(b_i\) alle \(2^i\) Operationen ändert. Wie bereits gesehen, ändert sich Bit \(b_4\) zum ersten Mal nach \(2^4 = 16\) Operationen.
Mit dieser Beobachtung können wir nun \(T(n)\) sogar genau ausrechnen: Bei \(n\) Operationen ändert sich Bit \(b_i\) somit genau \(\lfloor \frac{n}{2^i} \rfloor \)-mal
und Bits \(b_i\) mit \(i > \log_2 n\) ändern sich nie. D. h., Bit \(b_0\) ändert sich \(\frac{n}{2^0} = n\)-mal, Bit \(b_1\) ändert sich \(\left\lfloor\frac{n}{2^1}\right\rfloor = \left\lfloor\frac{n}{2}\right\rfloor\)-mal, Bit \(b_2\) ändert sich \(\left\lfloor\frac{n}{4}\right\rfloor\)-mal usw. Wenn wir dies nun über alle \(k\) Bits aufsummieren, dann erhalten wir für die
Gesamtzahl von Bitänderungen: \[T(n) = \sum_{i=0}^{k-1} \left \lfloor
\frac{n}{2^i} \right \rfloor \leq \sum_{i=0}^{k-1}
\frac{n}{2^i} = n \sum_{i=0}^{k-1} \frac{1}{2^i} < n \sum_{i=0}^{\infty} \frac{1}{2^i} \leq 2n \in \mathcal{O}(n).\]
Wir haben somit eine oberere Schanke für \(T(n)\), nämlich \(T(n) \leq 2n\), gefunden. Im Durchschnitt kostet somit jede increment-Operation nur \(2n/n = 2 \in \mathcal{O}(1)\).
Man beachte, dass die obere Schranke \(T(n) \in \mathcal{O}(n)\) viel kleiner und somit genauer ist als die Schranke \(T(n) \in \mathcal{O}(kn)\). (\(k\) könnte im Vergleich zu \(n\) riesig groß sein!)
Die Guthabenmethode
Die Idee der Guthabenmethode ist es, einige Operationen so zu besteuern, dass
sie effektiv die Kosten anderer Operationen mittragen. Wir tun also so,
als ob die Kosten dieser Operationen höher wären als ihre tatsächlichen Kosten.
Diese Kosten heißen amortisierte Kosten und der Differenzbetrag zu den
tatsächlichen Kosten wird dem sogenannten Guthaben hinzugefügt. Dieses
Guthaben wird dann genutzt, um die Kosten von Operationen zu tragen, deren
amortisierte Kosten niedriger als ihre tatsächlichen Kosten sind. Diese Methode wird auch oft als Bankkontomethode bezeichnet, die besteuerten Operationen zahlen mehr als sie eigentlich Kosten und die Differenz wird auf ein Bankkonto eingezahlt. Von diesem Bankkonto werden dann besonders teure Operationen subventioniert, so dass insgesamt alle Operationen nur geringe Kosten haben.
Die Kunst besteht hier in der geeigneten Wahl amortisierter Kosten, da
sichergestellt werden muss, dass das Guthaben bzw. der Kontostand niemals negativ wird. Dadurch erhält man durch die Summe der amortisierten Kosten eine obere Schranke an die Summe der tatäschlichen Kosten.
Betrachten wir das Beispiel des Binärzählers: Wir wählen die folgende Besteuerungsregel: Das Setzen eines Bits von \(0\) auf \(1\) kostet \(2\) (und somit mehr als tatsächlich nötig) und das Setzen eines
Bits von \(1\) auf \(0\) ist kostenlos (und kostet somit weniger als tatsächlich nötig).
Sei \(t_i\) die Anzahl der Bitflips bei der \(i\)-ten increment-Operation. D. h., \(t_i\) entspricht den tatsächlichen Kosten. Es gilt \[t_i = e_i + n_i,\] wobei \(e_i\) die Anzahl der Bitflips von \(1\) auf \(0\) und \(n_i\) die Anzahl der Bitflips von \(0\) auf \(1\) beschreibt.
Die amortisierten Kosten \(a_i\) der \(i\)-ten increment-Operation betragen somit \[a_i = 0\cdot e_i + 2\cdot n_i.\]
Wird ein Bit von \(0\) auf \(1\) gesetzt, dann wird somit eine Kosteneinheit auf das Bankkonto eingezahlt, da diese eine Kosteneinheit zu viel gezahlt wurde. Wird ein Bit von \(1\) auf \(0\) gesetzt, dann wird dafür eine Kosteneinheit vom Bankkonto abgehoben, um den Bitflip zu bezahlen. Betrachten wir als Beispiel, was passiert, wenn wir die Operation increment auf den Zählerstand \(01101111\) anwenden:
Das Guthaben vor der Operation beträgt \(6\), da jedes der sechs vorhandenen \(1\)-Bits irgendwann bei seiner Erzeugung eine Kosteneinheit auf das Bankkonto eingezahlt hat. \(0\)-Bits haben keinen Einfluss auf das Bankkonto, da diese entweder nie etwas eingezahlt haben oder deren Kosten, falls diese von \(1\) auf \(0\) geflippt wurden, bereits komplett beglichen wurden. Im Beispiel verändert sich das Guthaben von \(6\) auf \(3\) und somit um \(-3\). Insgesamt werden \(4\) Bits, nämlich \(b_0, b_1, b_2\) und \(b_3\), von \(1\) auf \(0\) gelippt und Bit \(b_4\) von \(0\) auf \(1\). Die \(4\) Bitflips von \(1\) auf \(0\) verringern das Guthaben um \(4\), da jeder dieser Flips eine Kosteneinheit vom Konto abhebt. Der Bitflip von \(0\) auf \(1\) von Bit \(b_4\) zahlt eine Kosteneinheit auf das Konto ein. Man kann sich das auch so vorstellen, dass neben jedem \(1\)-Bit eine Kosteneinheit platziert wird, von der dann ein eventueller Bitflip zurück auf \(0\) bezahlt wird.
Das Guthaben auf dem Bankkonto entspricht also zu jeder Zeit der Anzahl der auf \(1\) gesetzten Bits und ist daher nie negativ. Daraus folgt, dass immer genug Guthaben vorhanden ist, um alle Kosten zu bezahlen. Wir haben also \[T(n) = \sum_{i=1}^n t_i \le \sum_{i=1}^n a_i, \] d. h., wir müssen nun nur noch \(a_i\) für alle \(i\) abschätzen, um eine gültige obere Schranke für \(T(n)\) zu erhalten.
Für diese Abschätzung benötigen wir noch eine entscheidende Beobachtung: Bei jeder increment-Operation wird höchstens ein neues Bit von \(0\) auf \(1\) gesetzt. (Genauer: Es wird immer genau ein neues Bit auf \(1\) gesetzt, außer bei der increment-Operation auf \(x=2^k-1\), d. h., wenn alle \(k\) Bits den Wert \(1\) haben.) D. h., für alle \(i\) gilt \(n_i \leq 1\). Daher sind die amortisierten Kosten jeder Operation
höchstens \(2\cdot n_i \leq 2\) und es gilt
\[T(n) = \sum_{i=1}^n t_i \le \sum_{i=1}^n a_i \le 2 n \in \mathcal{O}(n).\]
Die Potentialmethode
Die Potentialmethode ist sehr eng mit der Guthabenmethode verwandt. Vom Prinzip her gehen wir ähnlich vor, doch die Besteuerungsregeln der einzelnen Operationen werden hierbei direkt vom Zustand der Datenstruktur hergeleitet. Man beachte, dass am Beispiel des Binärzählers die benutzte Besteuerungsregel recht willkürlich und ohne Rechtfertigung gewählt wurde.
Die Potentialmethode ist somit oft leichter anzuwenden als die Guthabenmethode, da wir uns nur darauf konzentrieren müssen, welchen Einfluss die untersuchten Operationen auf die Datenstruktur haben, und wir diesen Einfluss nur quantifizieren müssen.
Bei der Potentialmethode definieren wir eine sogenannte Potentialfunktion \(\Phi(i)\),
die nur vom aktuellen Zustand der Datenstruktur nach der \(i\)-ten Operation abhängt und z. B. auf eine natürliche Zahl abbildet. Ähnlich wie bei der Guthabenmethode kann ein positives Potential genutzt werden, um die Kosten zukünftiger Operationen zu bezahlen.
Wir wählen die Funktion \(\Phi\) so, dass \(\Phi(0)\ge 0\) gilt, d. h., das Ausgangspotential vor der Ausführung jeglicher Operationen ist nicht-negativ. Meist wählt man \(\Phi\) so, dass \(\Phi(0) = 0\) gilt.
Die amortisierten Kosten der \(i\)-ten Operation werden dann einfach als Summe der tatsächlichen Kosten und der Potentialänderung definiert:
\[a_i = t_i + \Phi(i)-\Phi(i-1).\]
Damit gilt dann für die Summe der amortisierten Kosten
\[\sum_{i=1}^n a_i = \sum_{i=1}^n \big(t_i + \Phi(i) - \Phi(i-1)\big) = \sum_{i=1}^n t_i + \Phi(n) - \Phi(0).\] Wenn wir also
sicherstellen können, dass für jedes \(i\) das Potential \(\Phi(i)\geq \Phi(0)\)
ist, dann ist die Summe der amortisierten Kosten eine gültige obere Schranke an die
Summe der tatsächlichen Kosten
\[T(n) = \sum_{i=1}^n t_i \leq \sum_{i=1}^n a_i.\]
Im Beispiel des Binärzählers wählen wir als Potentialfunktion \(\Phi\) die Anzahl der \(1\)-en in unserem Array nach der \(i\)-ten increment-Operation. Die Intuition dahinter ist, dass increment-Operationen nur dann teuer sind, wenn im Zähler viele \(1\)-Bits vorhanden sind. Falls aber eine solche teure Operation vorkommt, dann werden viele \(1\)-Bits auf \(0\) geflippt, und danach sind viel weniger \(1\)-Bits vorhanden. D. h., das Potential für eine weitere teure Operation ist damit drastisch gesunken. (Man könnte hier auch genauer sein und als Potential die Länge des zusammenhängenden \(1\)-Bit-Blocks am Ende des Zählers wählen.)
Mit dieser Wahl von \(\Phi\) gilt, dass \(\Phi(i)\) offenbar nie negativ ist und \(\Phi(0) = 0\) gilt. Angenommen die \(i\)-te Operation
setzte \(e_i\) Bits von \(1\) auf \(0\). Dann gilt für die Kosten dieser Operation \(t_i \leq
e_i + 1\), da höchstens ein neues Bit von \(0\) auf \(1\) gesetzt wird. Für das
neue Potential gilt \[\Phi(i) \leq \Phi(i-1) - e_i+1 \iff \Phi(i)-
\Phi(i-1) \leq 1-e_i.\]
Damit erhält man für die amortisierten Kosten der \(i\)-ten increment-Operation \[a_i = t_i + \Phi(i) -
\Phi(i-1) \leq e_i+1 + 1 -e_i = 2\]
und insgesamt wieder \[T(n) = \sum_{i=1}^n t_i \leq \sum_{i=1}^n a_i \leq 2n \in \mathcal{O}(n).\]
Bei genauem Hinsehen liefert uns die Potentialmethode die Erklärung, warum die Guthabenmethode eigentlich funktioniert. Die Veränderung des Guthabens auf dem Bankkonto entspricht genau der Potentialänderung einer zulässigen Potentialfunktion.
Aufgabe
Als Übungsanwendung betrachten wir einen speziellen Stack namens FlushStack.
Ein FlushStack arbeitet vom Prinzip her wie ein herkömmlicher Stack und hat somit die Operationen top(), welche das oberste Element des FlushStacks ausgibt (es jedoch nicht löscht), pop(), welche das oberste Element ausgibt und vom FlushStack löscht und push(x), welche das Element \(x\) auf den FlushStack legt. Der einzige Unterschied zu einem herkömmlichen Stack ist, dass ein FlushStack auch noch die Operation flush() anbietet, welche nacheinander alle Elemente des FlushStacks ausgibt und löscht.
Die Operationen top(), pop() und push(x) haben jeweils Kosten \(c\), für eine beliebige Konstante \(c>0\). Die Operation flush() auf einem FlushStack, welcher \(k\) Elemente enthält, kostet \(c \cdot k\).
Wir betrachten nun eine Folge von \(n\) Operationen auf einem anfangs leeren FlushStack. Jede der Operationen kann dabei top(), pop(), push(x) oder flush() sein. Es seien \(T(n)\) die Worstcase-Kosten einer solchen Operationenfolge.
Aufgabe a)
Zeige mittels herkömmlicher Worstcase-Analyse, dass \(T(n) \in \mathcal{O}(n^2)\) gilt.
Aufgabe b)
Benutze die Guthaben- oder die Potentialmethode, um zu zeigen, dass tatsächlich \(T(n) \in \mathcal{O}(n)\) gilt.
Lösung:
