Informatik Algorithmen – Amortisierte Analyse
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist der Unterschied zwischen amortisierter und durchschnittlicher Laufzeitanalyse…
Karten
15 KartenWas ist der Unterschied zwischen amortisierter und durchschnittlicher Laufzeitanalyse?
Rückseite
Amortisierte Analyse garantiert Schranken für jede Eingabefolge ohne Wahrscheinlichkeitsannahmen, durchschnittliche Analyse setzt Zufallsverteilung voraus.
Wie funktioniert die Aggregatmethode bei der amortisierten Analyse?
Rückseite
Gesamtkosten einer Operationsequenz durch Anzahl der Operationen teilen; ergibt obere Schranke für amortisierte Kosten pro Operation.
Was ist die Kernidee der Accounting-Methode (Buchhaltungsmethode)?
Rückseite
Operationen erhalten amortisierte Kosten; Überschuss wird als Guthaben gespeichert und zahlt spätere teure Operationen.
Wie definiert die Potentialmethode das Potential einer Datenstruktur?
Rückseite
Potential Φ maps Data Structure State to non-negative reell; amortisierte Kosten = tatsächliche Kosten + Φ(nachher) - Φ(vorher).
Welche amortisierten Kosten hat Push in einem Stack mit Multipop-Operation?
Rückseite
Push: 2 (1 für Push, 1 als Guthaben für späteres Pop). Pop/Multipop: 0 amortisiert, da durch Guthaben finanziert.
Warum hat Einfügen in ein dynamisches Array (Verdopplung) amortisiert O(1) Kosten?
Rückseite
Kopieren bei Vergrößerung kostet O(n), tritt aber nur alle n Einfügungen auf; Aggregate-Methode: (n·1 + n) / 2n ∈ O(1).
Was ist das Potential für einen Binärzähler mit k Bits bei der Potentialmethode?
Rückseite
Φ = Anzahl gesetzter Bits (1-Bits). Inkrement flippt Bits von 1→0 (Potential sinkt) und ein 0→1 (Potential steigt).
Wie hoch sind die amortisierten Kosten für Inkrement am Binärzähler?
Rückseite
2: tatsächliche Kosten = 1 + Anzahl trailing 1s; Potentialänderung = 1 - trailing 1s; Summe = 2.
Wann ist die Accounting-Methode der Potentialmethode vorzuziehen?
Rückseite
Wenn sich Guthaben intuitiv auf konkrete Elemente verteilen lässt (z. B. Stack-Elemente), ohne globale Potentialfunktion definieren zu müssen.
Was besagt das Potential-Methoden-Theorem für die Korrektheit?
Rückseite
Summe amortisierter Kosten ≥ Summe tatsächlicher Kosten, falls Φ(Start)=0 und Φ≥0 immer gilt.
Wie unterscheiden sich amortisierte Kosten von Worst-Case-Kosten einer einzelnen Operation?
Rückseite
Amortisierte Kosten sind Mittelwert über Sequenz; einzelne Operation kann teurer sein (z. B. Array-Verdopplung O(n) vs. amortisiert O(1)).
Was ist die amortisierte Kostenformel der Potentialmethode?
Rückseite
ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁), wobei cᵢ tatsächliche Kosten, Dᵢ Datenstruktur nach i-ter Operation.
Welches Potential eignet sich für einen Stack mit Multipop?
Rückseite
Φ = Stackgröße. Push erhöht Φ um 1 (amortisiert 2), Pop verringert Φ um 1 (amortisiert 0).
Warum funktioniert Verdopplung bei dynamischen Arrays, aber nicht Vergrößerung um konstantes k?
Rückseite
Bei +k tritt Vergrößerung alle k Einfügungen auf; Kopierkosten Σ n/k · n ∈ Θ(n²), amortisiert Θ(n) statt O(1).
Kann die amortisierte Analyse auch untere Schranken beweisen?
Rückseite
Nein, sie liefert nur obere Schranken für Sequenzen; untere Schranken erfordern adversarielle Argumente oder Informations-Theorie.