Amortized Analysis
Die amortisierte Analyse bewertet die obere Schranke der Gesamtkosten einer Operationssequenz, gemittelt pro Operation, auch wenn einzelne Operationen gelegentlich teuer sind.
Zweck
Analysiert die durchschnittliche Leistung von Datenstrukturen über Operationssequenzen, z. B. dynamische Array-Erweiterung.
Mechanismus
Drei Methoden: Aggregatanalyse (Gesamtkosten/Operationen), Accounting-Methode (günstige Operationen mehr belasten um teure zu subventionieren), Potential-Methode (Funktion Φ misst Zustandskomplexität). Dynamische Array-Einfügung: amortisiert O(1).
Anwendungsfälle
- Datenstruktur-Analyse
- Performance-Garantien
- Algorithmendesign