dynamisk arrayEdit
Tänk på en dynamisk array som växer i storlek som fler element läggs till, till exempel ArrayListi Java ellerSTD::VectorI C++. Om vi började med en dynamisk uppsättning av Storlek 4, kunde vi trycka 4 element på den, och varje operation skulle ta konstant tid. Men att trycka på ett femte element på den arrayen skulle ta längre tid eftersom arrayen skulle behöva skapa en ny array med dubbla nuvarande storlek (8), kopiera de gamla elementen till den nya arrayen och lägg sedan till det nya elementet. De kommande tre tryckoperationerna skulle på samma sätt ta konstant tid, och sedan skulle det efterföljande tillägget kräva ytterligare en långsam fördubbling av arraystorleken.
i allmänhet om vi betraktar ett godtyckligt antal pushar n + 1 till en matris av storlek n, märker vi att push-operationer tar konstant tid förutom den sista som tar {\displaystyle \Theta ( n)}
tid för att utföra storleksfördubblingsoperationen. Eftersom det fanns n + 1 operationer totalt kan vi ta genomsnittet av detta och upptäcka att trycka element på den dynamiska arrayen tar: N ( 1) + (1) + (1)+(1) = (1) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)} {n+1}}=\Theta (1)}
, konstant tid.
QueueEdit
visas är en rubinimplementering av en kö, en FIFO-datastruktur:
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
enqueue-operationen trycker bara på ett element på ingångsmatrisen; denna operation beror inte på längden på varken ingång eller utgång och körs därför i konstant tid.
men dequeue-operationen är mer komplicerad. Om utgångsmatrisen redan har några element i den, körs dequeue i konstant tid; annars tar dequeue O(n ) {\displaystyle O(n)}
tid för att lägga till alla element i utgångsmatrisen från ingångsmatrisen, där n är den aktuella längden på ingångsmatrisen. Efter att ha kopierat n-element från ingången kan vi utföra n dequeue-operationer, var och en tar konstant tid, innan utgångsmatrisen är tom igen. Således kan vi utföra en sekvens av n dequeue-operationer i endast O ( n ) {\displaystyle O(n)}
tid, vilket innebär att den avskrivna tiden för varje dequeue-operation är O ( 1 ) {\displaystyle O(1)}
