Geamortiseerde analyse

Dynamische arrayEdit

Geamortiseerde analyse van de push-bewerking voor een dynamische array

Overweeg een dynamische matrix die groter wordt als er meer elementen toegevoegd, zoals ArrayList in Java of std::vector in C++. Als we beginnen met een dynamische reeks van grootte 4, kunnen we er 4 elementen op duwen, en elke operatie zou constant tijd in beslag nemen. Maar het duwen van een vijfde element op die array zou langer duren omdat de array een nieuwe array zou moeten maken van het dubbele van de huidige grootte (8), de oude elementen kopiëren naar de nieuwe array, en dan het nieuwe element toevoegen. De volgende drie push-operaties zouden op dezelfde manier constant tijd in beslag nemen, en dan zou de volgende toevoeging nog een langzame verdubbeling van de array-grootte vereisen.

in het algemeen als we een willekeurig aantal pushes n + 1 beschouwen naar een array met grootte n, dan merken we dat push-operaties constant tijd vergen, behalve voor de laatste Die Θ ( n ) {\displaystyle \Theta (n)}

tijd neemt om de grootteverdubbeling uit te voeren. Aangezien er n + 1 operaties totaal waren kunnen we het gemiddelde hiervan nemen en vinden dat het duwen van elementen op de dynamische array duurt: n Θ ( 1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}

, constante tijd.

QueueEdit

getoond is een Ruby implementatie van een wachtrij, een FIFO data structuur:

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

De enqueue operatie duwt gewoon een element op de input array; deze operatie is niet afhankelijk van de lengte van invoer of uitvoer en draait daarom in constante tijd.

De dequeue operatie is echter ingewikkelder. Als de output array al enkele elementen bevat, dan draait dequeue in constante tijd; anders neemt dequeue O ( n ) {\displaystyle O(n)}

tijd om alle elementen toe te voegen aan de output array van de input array, waarbij n de huidige lengte van de input array is. Na het kopiëren van n elementen van input, kunnen we n dequeue operaties uitvoeren, elk neemt constant de tijd, voordat de output array weer leeg is. Dus kunnen we een reeks van n dequeue operaties uitvoeren in slechts O ( n ) {\displaystyle O(n)}

tijd, wat impliceert dat de geamortiseerde tijd van elke dequeue operatie O ( 1 ) {\displaystyle O(1)}