Dynamisk arrayEdit
Vurder en dynamisk matrise som vokser i størrelse som flere elementer legges til det, for eksempel arraylist i java eller std::vector i c++. Hvis vi startet med et dynamisk utvalg av størrelse 4, kunne vi skyve 4 elementer på den, og hver operasjon ville ta konstant tid. Likevel ville det ta lengre tid å skyve et femte element på den matrisen, da arrayet måtte lage et nytt utvalg av dobbelt den nåværende størrelsen (8), kopiere de gamle elementene til den nye matrisen, og deretter legge til det nye elementet. De neste tre push-operasjonene vil på samme måte ta konstant tid, og deretter vil det etterfølgende tillegget kreve en annen langsom dobling av matrisestørrelsen.
generelt hvis vi vurderer et vilkårlig antall push-operasjoner n + 1 til en matrise med størrelse n, merker vi at push-operasjoner tar konstant tid bortsett fra den siste som tar Θ ( n ) {\displaystyle \Theta (n)}
tid for å utføre størrelsesdoblingsoperasjonen. Siden det var n + 1 operasjoner totalt, kan vi ta gjennomsnittet av dette og finne ut at skyve elementer på det dynamiske arrayet tar: n Θ ( 1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {N\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, Konstant Tid.
QueueEdit
Vist Er En Ruby-implementering 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-operasjonen skyver bare et element på inngangsarrayen; denne operasjonen er ikke avhengig av lengden på enten inngang eller utgang og kjører derfor i konstant tid.
men dequeue-operasjonen er mer komplisert. Hvis utgangsarrayet allerede har noen elementer i det, kjører dequeue i konstant tid; ellers tar dequeue O ( n ) {\displaystyle O(n)}
tid for å legge til alle elementene på utgangsarrayet fra inngangsarrayet, hvor n er den nåværende lengden på inngangsarrayet. Etter kopiering n elementer fra inngang, kan vi utføre n dequeue operasjoner, hver tar konstant tid, før utgangen array er tom igjen. Dermed kan vi utføre en sekvens av n dequeue-operasjoner i bare O ( n ) {\displaystyle O(n)}
tid, noe som innebærer at amortisert tid for hver dequeue-operasjon er O ( 1 ) {\displaystyle o(1)}
