Amortisierte Analyse dynamischer Arrays

Amortisierte Analyse ist kein Erwartungswert. Erwartete Laufzeit mittelt über eine Wahrscheinlichkeitsverteilung oder Zufallsentscheidungen; amortisierte Analyse beschränkt die Gesamtkosten jeder zulässigen Operationsfolge. Bei dynamischen Arrays kann ein einzelnes Anhängen wegen einer Vergrößerung Θ(n) kosten. Über viele Anhänge verteilen sich diese Kopierkosten aber auf die ganze Folge. Die Garantie braucht also keine Zufallsannahme und sagt trotzdem nicht, dass jeder einzelne Aufruf schnell ist. Eine zufällige Eingabeverteilung ist für diesen Beweis nicht erforderlich; die Schranke gilt selbst für die ungünstige Folge. Auch ein ungünstiger Eingabeverlauf erfüllt diese Worst-Case-Garantie.

Definiere für Zustand i eine Potentialfunktion Φ_i. Die amortisierten Kosten sind ĉ_i=c_i+Φ_i−Φ_i−1. Beim Summieren heben sich alle inneren Potentialterme paarweise auf; übrig bleiben Σĉ=Σc+Φ_m−Φ₀. Damit gilt Σc=Σĉ+Φ₀−Φ_m. Ist das Anfangspotential null und das Endpotential nichtnegativ, sind die tatsächlichen Gesamtkosten höchstens die amortisierten Gesamtkosten. Das Potential bildet dabei angesammeltes Guthaben ab, das spätere teure Operationen bezahlt. Die Teleskopsumme macht sichtbar, dass Guthaben zwischen aufeinanderfolgenden Zuständen verschoben wird, nicht verloren geht. Das anfängliche Guthaben darf dabei nicht stillschweigend positiv angenommen werden. Es muss im Beweis explizit berücksichtigt sein.

Verdoppelt ein Array seine Kapazität, werden Kopiervorgänge mit wachsendem Abstand seltener. Für m Anhänge addieren sich kopierte Kapazitäten wie eine geometrische Reihe; ihre Summe bleibt kleiner als ungefähr 2m. Dazu kommen m direkte Schreiboperationen. Insgesamt entsteht O(m) Arbeit und damit O(1) amortisierte Kosten je Anhängen. Würde man die Kapazität dagegen bei jedem vollen Array nur um einen Platz erhöhen, summierten sich Kopien zu 1+2+…+m und verursachten Θ(m²) Gesamtarbeit. Die direkte Arbeit umfasst auch die regulären Schreibzugriffe, nicht nur die seltenen Kopieroperationen.

Wenn das Array voll ist, reserviert die Implementierung einen größeren Speicherblock und kopiert die vorhandenen Elemente. Bei n belegten Plätzen kann genau dieser Anhängevorgang Θ(n) Zeit benötigen. Die amortisierte Schranke beschreibt die Summe einer Operationsfolge, nicht die maximale Latenz jedes Aufrufs. Für Echtzeitanwendungen mit engen Pausengrenzen können inkrementelles Kopieren oder andere Datenstrukturen geeigneter sein. Der Unterschied zwischen Gesamtdurchsatz und Einzellatenz ist deshalb bei der Wahl der Struktur wichtig. Bei strikten Antwortzeitvorgaben muss deshalb die teuerste Einzeloperation separat betrachtet werden. Die Gesamtsumme sagt folglich nichts über eine harte maximale Aufrufzeit aus.

Die Potentialmethode eignet sich gut, wenn ein Zustand eine messbare Reserve enthält, etwa freie Plätze oder noch nicht verbrauchtes Guthaben. Bei einem dynamischen Array kann man Potential proportional zur Zahl belegter Plätze seit der letzten Verdopplung wählen. Ein Anhängen erhöht die Reserve; eine Vergrößerung verbraucht sie für Kopien. Die konkrete Funktion muss nichtnegativ bleiben und den teuren Schritt tatsächlich abdecken. Verschiedene gültige Potentiale können denselben asymptotischen Grenzwert beweisen. Wichtig ist, dass die gewählte Potentialfunktion jede mögliche Zustandsfolge abdeckt und nicht nur das Beispiel.