dynaaminen arrayEdit
pitää dynaamista ryhmää, joka kasvaa kokoa kun siihen lisätään useampia elementtejä, kuten ArrayListJava taiSTD::vektoriC++. Jos aloittaisimme dynaamisella kokoonpanolla, jonka koko on 4, voisimme työntää siihen 4 elementtiä, ja jokainen operaatio veisi jatkuvasti aikaa. Silti työntää viides elementti päälle, että array kestäisi kauemmin, koska array olisi luoda uusi array kaksinkertainen Nykyinen Koko (8), Kopioida Vanhat elementit päälle Uusi array, ja sitten lisätä uuden elementin. Kolme seuraavaa työntöoperaatiota vaatisivat samalla tavoin jatkuvaa aikaa, ja sitten seuraava lisäys vaatisi vielä yhden hilakokonaisuuden hitaan kaksinkertaistamisen.
Yleensä Jos tarkastelemme mielivaltaista määrää työntöjä N + 1 kokoiselle joukolle n, huomaamme, että työntöoperaatiot vievät vakioajan lukuun ottamatta viimeistä, joka vie Θ ( n ) {\displaystyle \Theta (n)}
aikaa koon kaksinkertaistamisoperaation suorittamiseen. Koska oli n + 1 operaatioita yhteensä voimme ottaa keskimäärin tämän ja todeta, että työntää elementtejä päälle dynaaminen array vie: n Θ ( 1 ) + Θ ( N ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (N)}{n+1}}=\Theta (1)} 
Jonoedit
esitetty on jonon rubiininen toteutus, FIFO-tietorakenne:
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-operaatio vain työntää elementin tulorivistöön; tämä operaatio ei riipu sen enempää syötön kuin lähdön pituuksista ja toimii siksi vakioajassa.
dequeue-operaatio on kuitenkin monimutkaisempi. Jos lähtöjoukossa on jo joitain alkuaineita, dequeue toimii vakioajassa; muuten dequeue vie O ( n ) {\displaystyle O(n)}
aikaa lisätä kaikki alkuaineet tuloryhmän lähtöjoukolle, missä n on tuloryhmän nykyinen pituus. Kun kopiointi n elementtejä tulosta, voimme suorittaa n dequeue operaatioita, jokainen kestää jatkuvasti aikaa, ennen lähtö array on tyhjä uudelleen. Näin voidaan suorittaa n dequeue-operaatioiden jono vain O ( n ) {\displaystyle O(n)}
aika, mikä tarkoittaa, että kunkin dequeue-operaation amortioitu aika on O ( 1 ) {\displaystyle O(1)}
