Amortisierte Zeit ist die Art und Weise, die Zeitkomplexität auszudrücken, wenn ein Algorithmus neben der Zeitkomplexität, die die meiste Zeit vorkommt, nur einmal die sehr schlechte Zeitkomplexität hat. Ein gutes Beispiel wäre eine ArrayList, eine Datenstruktur, die ein Array enthält und erweitert werden kann. Eine andere Definition von Stack Overflow ist die durchschnittliche Zeit, die pro Operation benötigt wird, wenn man viele Operationen durchführt.
Wenn ArrayList die Kapazität des Arrays erreicht, wird ein neues Array mit der doppelten Größe des alten Arrays erstellt und alle Elemente des alten Arrays in das neue Array kopiert. In ArrayList gibt es zwei Zeitkomplexe; einer ist O(1) und der andere ist O(n).
Wenn das Array in ihm seine Kapazität nicht erreicht hat und noch genügend Platz zum Einfügen von Elementen hat
Um in diesem Fall ein Element in das Array einzufügen, müssen wir das Element nur nach dem letzten Element einfügen.
Wenn das Array seine Kapazität erreicht hat und sich mit der verdoppelten Größe neu erstellen muss
Das Array hat seine Kapazität erreicht und wir haben keine freien Plätze mehr. Dann müssen wir ein brandneues Array mit der doppelten Größe erstellen. Das dauert O(n), wobei n die Kapazität des alten Arrays und der schlimmste Fall ist.
Um diese beiden Zeitkomplexitäten auszudrücken, gibt es die amortisierte Zeit. Was es tut, ist, uns den schlimmsten Fall beschreiben zu lassen, der jedes Mal eintritt, wenn das interne Array seine Kapazität erreicht.
Aber wenn es einmal passiert, wird es so lange nicht wieder passieren, dass die Kosten „amortisiert“ sind.“ (Cracking the Coding Interview 6th edition 43)
Wie beschreiben wir also die beiden Komplexitäten?
Im Fall der ArrayList können wir sagen, dass
Das Einfügen dauert O(n), wenn die Kapazität erreicht ist, und die amortisierte Zeit für jedes Einfügen ist O(1).
Aber lassen Sie uns die schlimmste Zeitkomplexität genau betrachten, ohne diese Zeit zu vereinfachen. Wenn die interne Array-Kapazität mit 1 beginnt, dann werden die Kapazitäten 1, 2, 4, 8, 16… X sein, wenn sie die Kapazität erreicht und verdoppelt wird. Je nach der erreichten Kapazität müssen 1, 2, 4, 8, 16… X Elemente in das neue Array kopiert werden. Die Zeitkomplexität beträgt also 1 + 2 + 4 + 8 + 16 +… X. Wenn man von X ausgeht, ist das ungefähr X + X/2 + X/4 + X/8… + 1 = 2X. Mit anderen Worten:
Das Einfügen dauert O(2X), wenn die Kapazität von X erreicht ist, und die amortisierte Zeit für jedes Einfügen ist O(1).
