Amortisierte Analyse

Die amortisierte Analyse begrenzt die durchschnittlichen Kosten pro Operation über eine Worst-Case-Sequenz von Operationen und zeigt, dass gelegentlich teure Operationen günstig sein können, wenn ihre Kosten auf viele günstige Operationen verteilt werden.

Definition

Die amortisierte Analyse ist eine Methode zur Begrenzung der Gesamtkosten einer Operationssequenz auf einer Datenstruktur und zur Division durch die Anzahl der Operationen, wodurch eine amortisierte Kosten pro Operation ermittelt wird, die im Worst Case über die gesamte Sequenz gilt, selbst wenn einzelne Operationen stark in den Kosten variieren.

Scope

Dieses Thema behandelt die drei Standardtechniken der amortisierten Analyse – die Aggregatmethode, die Buchhaltungsmethode (Banker's Method) und die Potenzialmethode – und ihre Anwendung auf Datenstrukturen, deren einzelne Operationen in den Kosten variieren, wie dynamische Arrays, Binärzähler, Splay-Bäume und die Disjoint-Set-Struktur (Union-Find). Es unterscheidet amortisierte Kosten von durchschnittlichen Kosten und Worst-Case-Kosten pro Operation.

Core questions

• Wie unterscheiden sich amortisierte Kosten von Worst-Case-Kosten pro Operation und durchschnittlichen Kosten?
• Wie begrenzt die Aggregatmethode die Gesamtkosten einer Operationssequenz?
• Wie weist die Buchhaltungsmethode Guthaben zu, um spätere teure Operationen zu bezahlen?
• Wie verwendet die Potenzialmethode eine Potenzialfunktion, um Kosten auszugleichen?
• Welche Datenstrukturen verlassen sich auf amortisierte Garantien statt auf pro-Operation-Grenzen?

Key concepts

• amortisierte Kosten
• Aggregatmethode
• Buchhaltungsmethode (Banker's Method)
• Potenzialmethode
• Potenzialfunktion
• Verdopplung dynamischer Arrays
• Inkrementierung von Binärzählern
• Union-Find mit Pfadkompression

Key theories

Potenzialmethode

Die Potenzialmethode weist dem Zustand der Datenstruktur ein nicht-negatives Potenzial zu; die amortisierten Kosten einer Operation sind ihre tatsächlichen Kosten plus die Änderung des Potenzials, sodass günstige Operationen Potenzial aufbauen, das spätere teure Operationen bezahlt.

Buchhaltungsmethode (Banker's Method)

Die Buchhaltungsmethode berechnet einige Operationen mehr als ihre tatsächlichen Kosten und speichert den Überschuss als Guthaben auf Datenstrukturelementen, um zukünftige teure Operationen zu bezahlen, wodurch sichergestellt wird, dass das Guthaben niemals negativ wird.

Clinical relevance

Die amortisierte Analyse erklärt, warum viele weit verbreitete Strukturen in der Praxis trotz gelegentlich kostspieliger Operationen effizient sind: Dynamische Arrays (resizable lists), Hash-Tabellen, die neu gehasht werden, Union-Find, das in Konnektivitäts- und Minimum-Spanning-Tree-Algorithmen verwendet wird, und selbstjustierende Strukturen wie Splay-Bäume verlassen sich alle auf amortisierte und nicht auf pro-Operation-Garantien.

History

Der Begriff und der systematische Rahmen für die amortisierte Analyse wurden 1985 von Robert Tarjan eingeführt, basierend auf früheren Ad-hoc-Argumenten. Die Technik war zentral für die Analyse der selbstjustierenden Datenstrukturen (Splay-Bäume, Fibonacci-Heaps), die von Tarjan und Sleator in den 1980er Jahren entwickelt wurden.

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

Sind amortisierte Kosten dasselbe wie durchschnittliche Kosten?

Nein. Durchschnittliche Kosten sind eine Erwartung über eine Wahrscheinlichkeitsverteilung von Eingaben und können durch eine unglückliche Eingabe verletzt werden. Amortisierte Kosten sind eine Worst-Case-Garantie über eine Sequenz von Operationen, bei der keine Zufälligkeit angenommen wird: Die Gesamtkosten einer solchen Sequenz sind begrenzt, sodass der Durchschnitt pro Operation immer gilt.

Warum ist das Anhängen an ein dynamisches Array amortisiert O(1), wenn die Größenänderung O(n) ist?

Weil das Array typischerweise seine Kapazität verdoppelt, sind Größenänderungen im Verhältnis zu Anhängen selten, und die gesamte Kopierarbeit über eine Sequenz von n Anhängen ist proportional zu n. Auf alle Anhänge verteilt, ergibt dies konstante amortisierte Kosten, obwohl eine einzelne Größenänderung linear ist.