Konstante Abschreibungsdauer

Question

Was ist mit "Constant Amortized Time" gemeint, wenn es um die Zeitkomplexität eines Algorithmus geht?

Answer 1

Die Leistung einer Funktion kann gemittelt werden, indem die "Gesamtzahl der Funktionsaufrufe" durch die "Gesamtzeit für alle diese Aufrufe" geteilt wird. Auch Funktionen, die bei jedem Aufruf immer länger brauchen, können auf diese Weise gemittelt werden.

Das Wesentliche einer Funktion, die bei Constant Amortized Time ist, dass diese "Durchschnittszeit" eine Obergrenze erreicht, die nicht überschritten wird, wenn die Zahl der Anrufe weiter steigt. Jeder einzelne Aufruf kann in seiner Leistung variieren, aber auf lange Sicht wird diese Durchschnittszeit nicht immer weiter ansteigen.

Das ist der wesentliche Vorzug einer Leistung, die auf Constant Amortized Time .

Answer 2

Amortisierte Laufzeit: Dies bezieht sich auf die Berechnung der algorithmischen Komplexität in Form von Zeit oder Speicherverbrauch pro Vorgang . Er wird verwendet, wenn die meisten Operationen schnell sind, aber bei einigen Gelegenheiten ist die Ausführung des Algorithmus langsam. Daher wird die Abfolge der Operationen untersucht, um mehr über die amortisierte Zeit zu erfahren.