Lektion 1.4

Amortisierte Analyse

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • erklären, warum ein dynamisches Array mit Verdopplung pro Anhängen amortisiert konstant viel kostet,

  • amortisierte Kosten mit der Aggregatmethode, der Buchhaltermethode und der Potentialmethode bestimmen,

  • den Binärzähler mit allen drei Methoden analysieren,

  • begründen, warum man ein Array erst bei Viertelfüllung halbiert,

  • amortisierte Kosten vom Durchschnittsfall unterscheiden.

Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation, Rekursion und Rekurrenzgleichungen

Listen in Python oder Java können beliebig wachsen: Du hängst ein Element nach dem anderen an, ohne vorher die Länge festzulegen. Im Speicher liegt aber ein Feld fester Länge. Ist es voll, muss das Programm ein größeres Feld anlegen und alle Elemente umkopieren. Bei einer Liste mit einer Million Elementen kostet dieses eine Anhängen eine Million Kopierschritte.

Die schlechteste Laufzeit einer einzelnen Operation ist also Θ(n)\Theta(n). Wer daraus schließt, dass nn Anhängeoperationen O(n2)O(n^2) kosten, hat zwar recht, aber die Schranke ist viel zu grob: Die teuren Operationen sind selten, und zwischen zwei teuren liegen viele billige.

Die amortisierte Analyse nimmt diese Beobachtung ernst. Sie schätzt die Gesamtkosten einer ganzen Folge von Operationen ab und verteilt sie gleichmäßig auf die einzelnen Operationen, wie man eine große Anschaffung auf viele Monate umlegt. Wahrscheinlichkeiten kommen dabei nicht vor: Das Ergebnis gilt für jede Folge, auch die ungünstigste.

Vermute zuerst

Ein Feld wird jedes Mal, wenn es voll ist, auf die doppelte Kapazität vergrößert, und alle Elemente werden umkopiert. Wie hoch sind die Gesamtkosten von nn Anhängeoperationen, beginnend mit einem leeren Feld?

Definition

Dynamisches Array mit Verdopplung

Ein dynamisches Array besteht aus einem Feld A\texttt{A} der Länge kap\texttt{kap} (Kapazität) und der Zahl groesse\texttt{groesse} der belegten Plätze. Es beginnt leer mit kap=0\texttt{kap} = 0. Anhängen:

ZeileEinrückungAnweisung
10anhaengen(x):\texttt{anhaengen(x):}
21wenn groesse = kap:\texttt{wenn groesse = kap:}
32neu = neues Feld der La¨nge max(1, 2 * kap)\texttt{neu = neues Feld der Länge max(1, 2 * kap)}
42fu¨r i von 0 bis groesse - 1: neu[i] = A[i]\texttt{für i von 0 bis groesse - 1: neu[i] = A[i]}
52A = neu; kap = max(1, 2 * kap)\texttt{A = neu; kap = max(1, 2 * kap)}
61A[groesse] = x\texttt{A[groesse] = x}
71groesse = groesse + 1\texttt{groesse = groesse + 1}

Als Kosten zählen wir die Schreibzugriffe auf Elemente: 11 für Zeile 6 und je 11 für jede Kopie in Zeile 4. Die ii-te Anhängeoperation kostet also ci=1c_i = 1, wenn Platz frei ist, und ci=ic_i = i, wenn vorher i−1i - 1 Elemente in einem vollen Feld lagen:

ii112233445566778899
cic_i112233115511111199
kap\texttt{kap} danach11224444888888881616
Definition

Amortisierte Kosten

Betrachte eine Datenstruktur, die leer beginnt, und eine Folge von nn Operationen mit tatsächlichen Kosten c1,…,cnc_1, \dots, c_n. Weist man jeder Operation einen Betrag c^i\hat c_i zu, sodass für jede solche Folge und jedes nn

∑i=1nc^i≥∑i=1nci\sum_{i=1}^{n} \hat c_i \ge \sum_{i=1}^{n} c_i

gilt, dann heißen die c^i\hat c_i amortisierte Kosten. Sind alle c^i≤C\hat c_i \le C für eine Konstante CC, so kosten nn Operationen zusammen höchstens C nC\,n, und man sagt, eine Operation kostet amortisiert O(1)O(1).

Das ist eine Garantie für den schlechtesten Fall, aber über die ganze Folge statt für jede einzelne Operation. Eine einzelne Operation darf teuer sein. Es gibt drei Methoden, amortisierte Kosten nachzuweisen.

Satz

Aggregatmethode für das dynamische Array

Die Aggregatmethode berechnet direkt die Gesamtkosten ∑ci\sum c_i und teilt durch nn. Für das dynamische Array mit Verdopplung gilt: nn Anhängeoperationen ab dem leeren Feld kosten zusammen weniger als 3n3n. Jede kostet also amortisiert höchstens 33.

∑i=1nci  =  n+∑j≥02j≤n−12j  <  3n\sum_{i=1}^{n} c_i \;=\; n + \sum_{\substack{j \ge 0 \\ 2^j \le n-1}} 2^j \;<\; 3n
Kurz geprüft

Wie hoch sind die tatsächlichen Gesamtkosten der ersten 99 Anhängeoperationen in der Tabelle oben?

Beispiel

Buchhaltermethode: jedes Element zahlt seinen Umzug im Voraus

Die Buchhaltermethode (auch Kontomethode) legt für jede Operation einen festen Preis c^\hat c fest. Ist der Preis höher als die tatsächlichen Kosten, wird der Rest als Guthaben in der Datenstruktur gespeichert, zum Beispiel an einem bestimmten Element. Eine teure Operation bezahlt aus dem Guthaben. Darf das Guthaben nie negativ werden, so sind die Gesamtkosten höchstens die Summe der Preise.

Beim dynamischen Array verlangen wir 33 pro Anhängen. Davon bezahlt 11 das Schreiben des neuen Elements, und 22 werden an diesem Element als Guthaben abgelegt.

Warum reicht das? Kurz nach einer Verdopplung von Kapazität mm auf 2m2m liegen mm alte Elemente im Feld, deren Guthaben für die Kopie gerade verbraucht wurde. Bis das Feld wieder voll ist, kommen mm neue Elemente dazu, die zusammen 2m2m Guthaben mitbringen. Die nächste Verdopplung kopiert genau 2m2m Elemente und wird damit vollständig bezahlt. Jedes neue Element bezahlt also seinen eigenen künftigen Umzug und den Umzug eines alten Elements, das nichts mehr hat.

c^=3:1 (eigenes Schreiben)  +  2 (Guthaben fu¨r spa¨tere Kopien)\hat c = 3: \qquad 1 \text{ (eigenes Schreiben)} \;+\; 2 \text{ (Guthaben für spätere Kopien)}

Die erste Verdopplung von 00 auf 11 kopiert nichts, die von 11 auf 22 kopiert ein Element mit Guthaben 22. Das Guthaben ist also nie negativ, und nn Operationen kosten höchstens 3n3n.

Definition

Potentialmethode

Statt Guthaben an einzelne Elemente zu heften, misst die Potentialmethode das gespeicherte Guthaben mit einer Funktion Φ\Phi (gesprochen „Phi“), die jedem Zustand DD der Datenstruktur eine reelle Zahl Φ(D)\Phi(D) zuordnet. Sei D0D_0 der leere Anfangszustand und DiD_i der Zustand nach der ii-ten Operation. Man verlangt Φ(D0)=0\Phi(D_0) = 0 und Φ(Di)≥0\Phi(D_i) \ge 0 für alle ii und definiert

c^i=ci+Φ(Di)−Φ(Di−1)\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}).

Eine billige Operation, die das Potential erhöht, spart an. Eine teure Operation, die das Potential stark senkt, gibt Erspartes aus. Beim Summieren heben sich die Potentiale bis auf das erste und das letzte weg (Teleskopsumme):

∑i=1nc^i=∑i=1nci+Φ(Dn)−Φ(D0)  ≥  ∑i=1nci\sum_{i=1}^{n} \hat c_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0) \;\ge\; \sum_{i=1}^{n} c_i
Schritt für Schritt

Potentialmethode für das dynamische Array

Wähle Φ=2⋅groesse−kap\Phi = 2 \cdot \texttt{groesse} - \texttt{kap}. Am Anfang ist Φ=0\Phi = 0. Nach jeder Operation ist das Feld mindestens halb voll, also Φ≥0\Phi \ge 0.

  1. Anhängen ohne Vergrößern: ci=1c_i = 1, groesse\texttt{groesse} steigt um 11, kap\texttt{kap} bleibt. Also steigt Φ\Phi um 22:

    c^i=1+2=3\hat c_i = 1 + 2 = 3
Schritt 1 von 3
Beispiel

Der Binärzähler mit allen drei Methoden

Ein Zähler aus kk Bits B[0],…,B[k-1]\texttt{B[0]}, \dots, \texttt{B[k-1]} beginnt bei 00; B[0]\texttt{B[0]} ist das niedrigste Bit. Erhöhen um 11 setzt die Einsen am Ende auf 00 und die erste Null auf 11:

ZeileEinrückungAnweisung
10erhoehe(B):\texttt{erhoehe(B):}
21i = 0\texttt{i = 0}
31solange i < k und B[i] = 1:\texttt{solange i < k und B[i] = 1:}
42B[i] = 0; i = i + 1\texttt{B[i] = 0; i = i + 1}
51wenn i < k: B[i] = 1\texttt{wenn i < k: B[i] = 1}

Die Kosten sind die Zahl der geänderten Bits. Von 01110111 nach 10001000 ändern sich vier Bits, von 10001000 nach 10011001 nur eines. Die ersten acht Erhöhungen kosten 1,2,1,3,1,2,1,41, 2, 1, 3, 1, 2, 1, 4, zusammen 1515. Eine einzelne Erhöhung kann kk kosten.

Aggregat: Bit jj ändert sich bei jeder 2j2^j-ten Erhöhung, in nn Erhöhungen also ⌊n/2j⌋\lfloor n/2^j \rfloor Mal. Zusammen sind das weniger als n(1+12+14+… )=2nn(1 + \frac 12 + \frac 14 + \dots) = 2n.

Buchhalter: Preis 22. Davon bezahlt 11 das Setzen eines Bits auf 11, und 11 bleibt als Guthaben an diesem Bit liegen. Wird das Bit später auf 00 gesetzt, bezahlt es das selbst. Jede Eins trägt also stets 11 Guthaben.

Potential: Φ\Phi ist die Zahl der Einsen. Sind B[0]\texttt{B[0]} bis B[t-1]\texttt{B[t-1]} Einsen, B[t]\texttt{B[t]} aber eine Null (mit t<kt < k), kostet die Erhöhung t+1t + 1, und die Zahl der Einsen ändert sich um 1−t1 - t:

c^=(t+1)+(1−t)=2\hat c = (t + 1) + (1 - t) = 2

Läuft der Zähler über (alle kk Bits sind 11), kostet die Erhöhung kk und Φ\Phi fällt um kk, also c^=0\hat c = 0. In jedem Fall ist c^≤2\hat c \le 2, und nn Erhöhungen ab 00 ändern weniger als 2n2n Bits, unabhängig von kk.

Kurz geprüft

Ein Feld wird nicht verdoppelt, sondern bei jedem Vollsein um genau einen Platz vergrößert (Kapazität 0,1,2,3,…0, 1, 2, 3, \dots). Wie viele Kopien entstehen bei 1010 Anhängeoperationen ab dem leeren Feld?

Beispiel

Schrumpfen: warum erst bei einem Viertel halbieren?

Wenn Elemente am Ende entfernt werden, soll das Feld wieder kleiner werden, damit nicht viel Speicher leer bleibt. Entfernen kostet 11, Halbieren der Kapazität kopiert alle Elemente in ein halb so langes Feld.

Naheliegend wäre: halbieren, sobald das Feld nur noch halb voll ist. Nimm ein volles Feld mit 1616 Elementen und Kapazität 1616, und hänge dann abwechselnd an und entferne:

OperationKostenFüllstand / Kapazität danach
anhängen16+1=1716 + 1 = 1717/3217 / 32
entfernen, halbieren1+16=171 + 16 = 1716/1616 / 16
anhängen171717/3217 / 32
entfernen, halbieren171716/1616 / 16

Jede Operation kostet etwa nn, eine Folge von nn solchen Operationen Θ(n2)\Theta(n^2). Das Feld springt an der Grenze hin und her.

Die Lösung: halbieren erst, wenn nach dem Entfernen nur noch ein Viertel belegt ist (groesse=kap/4\texttt{groesse} = \texttt{kap}/4, für kap≥4\texttt{kap} \ge 4). Nach jeder Größenänderung ist das Feld dann ungefähr halb voll. Bis zur nächsten Änderung muss es entweder ganz voll werden (etwa kap2\frac{\texttt{kap}}{2} Anhängeoperationen) oder auf ein Viertel fallen (etwa kap4\frac{\texttt{kap}}{4} Entfernungen). Die nächste Größenänderung kopiert höchstens kap\texttt{kap} Elemente, und davor liegen mindestens etwa kap4\frac{\texttt{kap}}{4} billige Operationen, die sie bezahlen können. Im Beispiel oben kosten dieselben 4040 abwechselnden Operationen zusammen nur 5656 statt 680680.

Φ={2⋅groesse−kap,groesse≥kap/2kap/2−groesse,groesse<kap/2\Phi = \begin{cases} 2 \cdot \texttt{groesse} - \texttt{kap}, & \texttt{groesse} \ge \texttt{kap}/2 \\ \texttt{kap}/2 - \texttt{groesse}, & \texttt{groesse} < \texttt{kap}/2 \end{cases}

Mit diesem Potential rechnet man nach, dass jede Operation, Anhängen wie Entfernen, amortisiert höchstens 33 kostet. Das Potential wächst, wenn sich der Füllstand von der Hälfte entfernt, nach oben wie nach unten, und spart so für die nächste Größenänderung an. Eine der Rechnungen führst du in den Übungen.

Häufige Fehler

Amortisiert heißt nicht „im Durchschnitt bei zufälligen Eingaben“

Man liest „Anhängen kostet amortisiert O(1)O(1)“ und schließt: Im Durchschnitt über alle möglichen Eingaben ist Anhängen schnell, aber bei ungünstigen Eingaben kann eine lange Folge von Operationen trotzdem quadratisch teuer werden. Oder umgekehrt: Jede einzelne Operation ist in O(1)O(1).

Richtig ist

Beides stimmt nicht. Die amortisierte Schranke gilt für jede Folge von Operationen, auch die ungünstigste, ohne Wahrscheinlichkeiten. Sie garantiert die Gesamtkosten O(n)O(n), nicht die Kosten jeder einzelnen Operation: Ein einzelnes Anhängen kann Θ(n)\Theta(n) kosten. Die Durchschnittsanalyse dagegen mittelt über zufällige Eingaben. Quicksort mit dem ersten Element als Pivot braucht im Mittel über alle Anordnungen Θ(nlog⁡n)\Theta(n \log n) Vergleiche, auf einer sortierten Eingabe aber Θ(n2)\Theta(n^2), und das jedes Mal. Wo jede einzelne Operation schnell sein muss, etwa in Echtzeitsystemen, hilft eine amortisierte Schranke nicht.

Zusammenfassung

  • Amortisierte Analyse schätzt die Gesamtkosten einer Folge von Operationen im schlechtesten Fall ab und verteilt sie auf die Operationen.

  • Ein dynamisches Array mit Verdopplung kostet für nn Anhängeoperationen weniger als 3n3n, also amortisiert O(1)O(1) pro Operation, obwohl eine einzelne Θ(n)\Theta(n) kosten kann.

  • Aggregatmethode: Gesamtkosten direkt summieren, hier mit einer geometrischen Summe.

  • Buchhaltermethode: fester Preis pro Operation, der Überschuss liegt als Guthaben in der Datenstruktur und darf nie negativ werden.

  • Potentialmethode: c^i=ci+Φ(Di)−Φ(Di−1)\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) mit Φ(D0)=0\Phi(D_0) = 0 und Φ≥0\Phi \ge 0; die Summe teleskopiert.

  • Binärzähler: nn Erhöhungen ändern weniger als 2n2n Bits; Potential ist die Zahl der Einsen.

  • Wachstum um einen konstanten Faktor ist nötig; Wachstum um eine konstante Zahl führt zu Θ(n2)\Theta(n^2). Halbiert wird erst bei Viertelfüllung, sonst springt das Feld an der Grenze hin und her.

  • Amortisiert ist eine Garantie für jede Folge, keine Aussage über zufällige Eingaben und keine Schranke für jede einzelne Operation.

Übungen

Aufgabe 1Numerisch

Ein dynamisches Array mit Verdopplung beginnt leer mit Kapazität 00. Wie hoch sind die tatsächlichen Gesamtkosten (Schreibzugriffe einschließlich Kopien) von 1616 Anhängeoperationen?

Aufgabe 2Numerisch

Ein Binärzähler mit genügend vielen Bits beginnt bei 00 und wird 3232-mal erhöht. Wie viele Bits ändern sich insgesamt?

Aufgabe 3Numerisch

Ein Feld wächst immer um 44 Plätze, wenn es voll ist (Kapazität 0,4,8,12,…0, 4, 8, 12, \dots). Wie viele Kopien entstehen bei 2020 Anhängeoperationen ab dem leeren Feld?

Aufgabe 4Multiple Choice

Was garantiert die Aussage „Diese Operation kostet amortisiert O(1)O(1)“ für eine Datenstruktur, die leer beginnt?

Aufgabe 5Freitext

Ein dynamisches Array verdreifacht seine Kapazität, wenn es voll ist (Kapazität 0,1,3,9,27,…0, 1, 3, 9, 27, \dots). Zeige mit der Aggregatmethode, dass nn Anhängeoperationen ab dem leeren Feld zusammen weniger als 2,5 n2{,}5\,n Schreibzugriffe kosten.

Aufgabe 6Freitext

Der Binärzähler mit kk Bits soll jetzt auch vermindern können (um 11 verringern; dabei werden die Nullen am Ende zu Einsen und die letzte Eins zu einer Null). Zeige, dass dann nn Operationen ab einem geeigneten Zählerstand Θ(n⋅k)\Theta(n \cdot k) Bitänderungen kosten können. Warum versagt das Potential „Zahl der Einsen“?

Aufgabe 7Freitext

Das Feld halbiert seine Kapazität, wenn nach dem Entfernen groesse=kap/4\texttt{groesse} = \texttt{kap}/4 gilt (kap≥4\texttt{kap} \ge 4). Zeige mit dem Potential aus der Lektion (Φ=2⋅groesse−kap\Phi = 2 \cdot \texttt{groesse} - \texttt{kap} für groesse≥kap/2\texttt{groesse} \ge \texttt{kap}/2, sonst Φ=kap/2−groesse\Phi = \texttt{kap}/2 - \texttt{groesse}), dass ein Entfernen mit Halbieren amortisiert höchstens 33 kostet.