Amortisierte Analyse.

Eine ArrayList-Insertion ist normalerweise O(1), außer beim Resizing, wo sie O(n) wird. Wie misst man das fair? Antwort: amortisierte Analyse. Statt die Worst-Case-Kosten pro Operation zu nehmen, betrachtest du den Gesamt-Aufwand über eine Folge von Operationen, und teilst durch die Anzahl. Klausur-Pflicht in 8/17 WInf-Algo-Klausuren.

Die Idee in einem Satz

Amortisierte Kosten einer Operation = Gesamt-Kosten einer Folge von n Operationen ÷ n.

So bekommen seltene teure Operationen einen "fairen" durchschnittlichen Preis pro Operation.

Beispiel: Dynamisches Array (ArrayList)

arr.add(x):
    if size < capacity:
        arr[size++] = x       # O(1)
    else:
        new_arr = new Array[2 · capacity]
        copy all elements     # O(n), selten!
        arr = new_arr
        arr[size++] = x

Worst-Case pro Operation: O(n) (beim Resizing). Amortisierte Kosten pro Operation: O(1).

Warum? Bei n Inserts wird Resize bei Größen 1, 2, 4, 8, 16, ..., n ausgelöst. Gesamt-Kopier-Kosten: 1 + 2 + 4 + ... + n = 2n - 1 = O(n)

Plus n einzelne Inserts → Gesamt O(n) → pro Operation O(1) amortisiert.

Drei Methoden der amortisierten Analyse

1. Aggregat-Methode (Aggregate Analysis)

Direkt: Berechne T(n) = Gesamt-Kosten für n Operationen, teile durch n.

Beispiel ArrayList: T(n) = O(n) → amortisiert O(1).

Einfach, aber unflexibel, alle Operationen bekommen den GLEICHEN amortisierten Preis.

2. Accounting-Methode (Banker's Method)

Idee: Du speicherst "Geld" (Credits) bei billigen Operationen, das du später für teure Operationen ausgibst.

Beispiel ArrayList:

• Bei jedem Insert: lege 3 Credits hin.
• Davon: 1 für den eigentlichen Insert.
• 2 als "Reserve" für späteres Kopieren.
• Beim Resize: 2 · (Anzahl bisheriger Inserts) Credits sind vorhanden, deckt das Kopieren ab.

→ Amortisiert O(3) = O(1) pro Insert.

3. Potential-Methode

Idee: Definiere eine Potential-Funktion Φ(D_i) über den Zustand der Datenstruktur. Amortisierte Kosten = tatsächliche Kosten + Änderung des Potentials.

a_i = c_i + Φ(D_i) - Φ(D_(i-1))

Beispiel ArrayList: Φ(D_i) = 2 · (size - capacity/2). Bei billigen Inserts steigt Φ um 2. Bei Resize sinkt Φ, deckt damit den hohen c_i ab.

Komplexere Methode, aber sehr flexibel.

Klassische Beispiele

1. ArrayList Resize

Amortisiert O(1) pro Insert.

2. Stack mit Multi-Pop

MultiPop(k): pop k Elemente. Worst: O(k). Amortisiert über alle Operationen: O(1).

3. Binärzähler-Inkrement

Inkrementiere einen k-Bit-Zähler. Worst: O(k) (alle Bits flippen). Amortisiert: O(1) pro Inkrement.

4. Union-Find (Disjoint Set)

union und find Operationen mit Path-Compression + Union-by-Rank: amortisiert nahezu O(1) pro Operation (genauer: O(α(n))).

5. Splay-Trees

Splay-Operation: Worst-Case O(n), amortisiert O(log n).

6. Fibonacci-Heap

DecreaseKey amortisiert O(1), ExtractMin amortisiert O(log n).

Wichtige Unterscheidung

Amortisiert ≠ Average. Amortisierte Analyse macht KEINE Annahmen über die Verteilung der Eingaben, sie ist eine WORST-CASE-Aussage über die Gesamt-Folge.

Wofür ist amortisierte Analyse gut?

• Datenstrukturen mit gelegentlich teuren Operationen: Resize, Garbage Collection, Splay
• Worst-Case-Garantien für Folgen: wichtig bei real-time-Systemen mit Budgets pro Folge
• Faire Vergleiche: "Stack-Push ist O(1)" gilt amortisiert, auch wenn einzelne Pushes teuer sind

Anti-Beispiel: was NICHT amortisierbar ist

Suche in einem binären Suchbaum mit Worst-Case O(n): kann keine amortisierte Garantie geben, wenn der Baum entartet ist und du immer am tiefsten Ast suchst. Amortisierung hilft NICHT, wenn JEDE Operation gleich teuer sein kann.

→ AVL/Rot-Schwarz lösen das anders: durch BALANCE.

Klausur-Faustregeln

1. Amortisiert = Gesamt-Kosten ÷ Anzahl Operationen. Worst-Case der Folge, nicht der Einzeloperationen.

2. 3 Methoden: Aggregat, Accounting (Banker), Potential.

3. Klassiker: ArrayList Resize, Multi-Pop Stack, Binärzähler, Union-Find.

4. Amortisiert ≠ Average. Amortisiert macht keine Annahmen über Eingabe-Verteilung.

5. Verdoppelungs-Strategie ist Schlüssel. Bei Resize um Faktor 2 (statt +1) → amortisiert O(1).

Häufige Stolpersteine

1. Amortisiert mit Average verwechseln. Average: Erwartungswert über zufällige Eingaben. Amortisiert: Worst-Case über Folgen. Verschiedene Konzepte!

2. Linear-Resize statt Verdoppelung. ArrayList mit Resize um +10 hätte Worst O(n²) über n Inserts (nicht amortisiert O(1)). VERDOPPELUNG (·2) ist essentiell.

3. Vergessen, dass amortisiert NICHT pro Operation gilt. Wenn eine ArrayList am Limit ist, kann der NÄCHSTE Insert O(n) kosten. Amortisierung garantiert nur, dass die GESAMT-Folge gut ist.

4. Potential-Methode zu kompliziert anwenden. Bei einfachen Beispielen (ArrayList) ist Aggregat einfacher.

5. Amortisierte Analyse für nicht-deterministische Datenstrukturen. Funktioniert nur bei Datenstrukturen mit deterministischem Verhalten.

ArrayList-Resize-Lab

Sieh, wie eine ArrayList über 16 Inserts wächst:

• Standard-Kapazität verdoppelt sich bei jedem Resize
• Tatsächliche Kosten pro Insert (oft 1, manchmal viel)
• Amortisierte Kosten im Durchschnitt (immer ca. 3 = O(1))
• Resize-Ereignisse hervorgehoben

So wird amortisierte Analyse zur intuitiven Sache.

Klausur-Tipp: Bei Klausur-Aufgaben zur amortisierten Analyse, IMMER die Verdoppelungs-Strategie hervorheben. Wenn das Array um Faktor 2 wächst, summieren sich die Kopier-Kosten zu 1 + 2 + 4 + ... + n = 2n - 1 = O(n). Bei n Inserts → O(1) amortisiert.

Amortisierte Analyse, Praxis-Übung

6 Aufgaben zu amortisierten Kosten, Methoden, klassischen Beispielen.