Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Eine ArrayList-Insertion ist normalerweise — außer beim Resizing, wo sie 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.
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 . Bei Inserts → amortisiert.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Amortisierte Kosten einer Operation = Gesamt-Kosten einer Folge von
nOperationen ÷n.
So bekommen seltene teure Operationen einen "fairen" durchschnittlichen Preis pro Operation.
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.
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.
Idee: Du speicherst "Geld" (Credits) bei billigen Operationen, das du später für teure Operationen ausgibst.
Beispiel ArrayList:
→ Amortisiert O(3) = O(1) pro Insert.
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.
Amortisiert O(1) pro Insert.
MultiPop(k): pop k Elemente. Worst: O(k). Amortisiert über alle Operationen: O(1).
Inkrementiere einen k-Bit-Zähler. Worst: O(k) (alle Bits flippen). Amortisiert: O(1) pro Inkrement.
union und find Operationen mit Path-Compression + Union-by-Rank: amortisiert nahezu O(1) pro Operation (genauer: O(α(n))).
Splay-Operation: Worst-Case O(n), amortisiert O(log n).
DecreaseKey amortisiert O(1), ExtractMin amortisiert O(log n).
| Begriff | Bedeutung |
|---|---|
| Worst-Case pro Operation | Maximum-Kosten EINER einzelnen Operation |
| Amortisierte Kosten | Durchschnittliche Kosten pro Operation in einer Folge |
| Average-Case | Erwartungswert über zufällige Eingaben |
Amortisiert ≠ Average. Amortisierte Analyse macht KEINE Annahmen über die Verteilung der Eingaben — sie ist eine WORST-CASE-Aussage über die Gesamt-Folge.
O(1)" gilt amortisiert, auch wenn einzelne Pushes teuer sindSuche 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.
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).
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.
Sieh, wie eine ArrayList über 16 Inserts wächst:
O(1))So wird amortisierte Analyse zur intuitiven Sache.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
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.
6 Aufgaben zu amortisierten Kosten, Methoden, klassischen Beispielen.
Klausurfragen mit Lösungen (6)
Antwort: Gesamt-Kosten einer Folge von n Operationen ÷ n
Erklärung: Amortisierte Komplexität: TOTAL der Kosten über N Operationen / N. Gibt durchschnittlichen Preis pro Operation in einer Folge. Worst-Case-Garantie für die Folge, nicht für jede einzelne Operation.
Antwort: O(1)
Erklärung: Amortisiert O(1)! Auch wenn einzelne Inserts O(n) sind (beim Resize), summieren sich die Kopier-Kosten über n Inserts zu O(n) — durchschnittlich also O(1) pro Insert.
Antwort: Falsch
Erklärung: FALSCH. Average-Case: Erwartungswert über zufällige Eingaben (probabilistisch). Amortisiert: WORST-CASE-Garantie über eine ganze Folge (deterministisch). Verschiedene Konzepte, oft verwechselt.
Typ: Wahr/Falsch
Antwort: Dynamisches Array mit Resize
Erklärung: Dynamisches Array mit Resize: gelegentlich teure Operationen (O(n) beim Resize), aber amortisiert O(1) durch Verdoppelung. Andere Strukturen sind oft konstant teuer pro Operation.
Richtige Antworten: Drei Methoden: Aggregat, Accounting, Potential; Amortisiert ist WORST-CASE über Folgen; Union-Find ist amortisiert nahezu O(1); Splay-Trees sind amortisiert O(log n); Average-Case macht probabilistische Annahmen
Erklärung: Richtig: 3 Methoden, WORST über Folgen, Union-Find α(n), Splay O(log n), Average probabilistisch. Falsch: LINEAR-Resize ist O(n²) total → O(n) amortisiert; nur VERDOPPELUNG gibt O(1).
Typ: Multi-Select
Zuordnungen:
Erklärung: Klassische amortisierte Analysen. Alle haben gelegentlich teure Operationen, aber durchschnittlich gut.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: 7
Erklärung: Resizes bei Größen 1, 2, 4 → Kopier-Operationen: 1+2+4 = 7. Bei Resize zur Größe 8 wären 8 Kopien. Bei n=8 wird der 8-Resize nicht ausgelöst (passt ja schon). Antwort: 1+2+4 = 7 Kopien total + 8 Inserts = 15 Operationen.
Antwort: Wahr
Erklärung: RICHTIG. Banker's Method: Bei jeder billigen Operation legst du extra 'Credits' an (z.B. 3 statt 1). Bei teuren Operationen ziehst du die gesparten Credits zur Bezahlung heran. Über die Folge: total Credits gegeben ≥ total tatsächliche Kosten.
Typ: Wahr/Falsch
Antwort: O(n) — Resize bei jeder Operation!
Erklärung: Bei +1-Resize: JEDER Insert braucht Resize + Kopie. Total: 1+2+3+...+n = n(n+1)/2 = O(n²). Pro Operation: O(n) amortisiert. Verdoppelung ist KRITISCH für O(1) amortisiert!
Antwort: Potential-Methode
Erklärung: Potential-Methode: Definiere Φ(D_i) als 'Energie' der Datenstruktur nach Op i. Amortisierte Kosten = c_i + Φ(D_i) - Φ(D_{i-1}). Bei Resize sinkt Φ stark und deckt den hohen c_i.
Lösungen pro Lücke:
Erklärung: Amortisiert-Vokabular. Gesamt/Anzahl, 3 Methoden, O(1) bei Verdoppelung.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Aggregat-Methode: Total / n. ArrayList-Verdoppelung gibt amortisiert konstante Kosten pro Insert.
Typ: Reihenfolge