Dynamic arrayEdit
Betrachten Sie ein dynamisches Array, das größer wird, wenn mehr Elemente hinzugefügt werden, wie z. B ArrayList in Java oder std::vector in C++. Wenn wir mit einem dynamischen Array der Größe 4 beginnen würden, könnten wir 4 Elemente darauf schieben, und jede Operation würde eine konstante Zeit in Anspruch nehmen. Das Verschieben eines fünften Elements auf dieses Array würde jedoch länger dauern, da das Array ein neues Array mit der doppelten aktuellen Größe (8) erstellen, die alten Elemente in das neue Array kopieren und dann das neue Element hinzufügen müsste. Die nächsten drei Push-Operationen würden in ähnlicher Weise eine konstante Zeit in Anspruch nehmen, und dann würde die nachfolgende Addition eine weitere langsame Verdoppelung der Array-Größe erfordern.
Im Allgemeinen, wenn wir eine beliebige Anzahl von Pushs n + 1 zu einem Array der Größe n betrachten, stellen wir fest, dass Push-Operationen eine konstante Zeit benötigen, mit Ausnahme der letzten, die Θ ( n ) {\displaystyle \Theta (n)}
Zeit benötigt, um die Größenverdopplungsoperation durchzuführen. Da es insgesamt n + 1 Operationen gab, können wir den Durchschnitt davon nehmen und feststellen, dass das Verschieben von Elementen auf das dynamische Array dauert: n Θ (1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, Konstante zeit.
QueueEdit
Gezeigt ist eine Ruby-Implementierung einer Queue, einer FIFO-Datenstruktur:
class Queue def initialize @input = @output = end def enqueue(element) @input << element end def dequeue if @output.empty? while @input.any? @output << @input.pop end end @output.pop endend
Die Enqueue-Operation schiebt nur ein Element auf das Eingabearray; Diese Operation hängt nicht von der Länge der Eingabe oder Ausgabe ab und läuft daher in konstanter Zeit ab.
Die Dequeue-Operation ist jedoch komplizierter. Wenn das Ausgabearray bereits einige Elemente enthält, läuft dequeue in konstanter Zeit; andernfalls benötigt dequeue O ( n ) {\displaystyle O(n)}
Zeit, um alle Elemente aus dem Eingabearray in das Ausgabearray einzufügen, wobei n die aktuelle Länge des Eingabearrays ist. Nach dem Kopieren von n Elementen aus der Eingabe können wir n Dequeue-Operationen ausführen, die jeweils eine konstante Zeit in Anspruch nehmen, bevor das Ausgabearray wieder leer ist. Somit können wir eine Folge von n Dequeue-Operationen nur in O ( n ) {\displaystyle O(n)}
Zeit durchführen, was bedeutet, dass die amortisierte Zeit jeder Dequeue-Operation O (1 ) {\displaystyle O(1)}
