matrice dinamică
luați în considerare o matrice dinamică care crește în dimensiune pe măsură ce i se adaugă mai multe elemente, cum ar fi ArrayList în Java sau std::vector în C++. Dacă am începe cu o matrice dinamică de dimensiunea 4, am putea împinge 4 elemente pe ea și fiecare operație ar dura un timp constant. Cu toate acestea, împingerea unui al cincilea element pe acea matrice ar dura mai mult, deoarece matricea ar trebui să creeze o nouă matrice de dublu dimensiunea curentă (8), să copieze elementele vechi pe noua matrice și apoi să adauge noul element. Următoarele trei operații de împingere ar dura în mod similar un timp constant, iar apoi adăugarea ulterioară ar necesita o altă dublare lentă a dimensiunii matricei.
în general, dacă luăm în considerare un număr arbitrar de împingeri n + 1 la o matrice de dimensiune n, observăm că operațiunile de împingere durează constant, cu excepția ultimei care ia timpul de dublare a mărimii ( n ) {\displaystyle \Theta (n)}
pentru a efectua operația de dublare a mărimii. Din moment ce au existat N + 1 Total operațiuni putem lua media acestui și pentru a găsi că împingând elemente pe matrice dinamică ia: N ( 1) + (N ) N + 1 = (1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{N+1}}=\Theta (1)}
, timp constant.
QueueEdit
prezentat este o implementare Ruby a unei cozi, o structură de date FIFO:
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
operațiunea enqueue împinge doar un element pe matricea de intrare; această operație nu depinde de lungimile de intrare sau de ieșire și, prin urmare, rulează în timp constant.
cu toate acestea, operațiunea dequeue este mai complicată. Dacă matricea de ieșire are deja unele elemente în ea, atunci dequeue rulează în timp constant; în caz contrar, dequeue ia O ( n ) {\displaystyle o(n)}
timp pentru a adăuga toate elementele pe matricea de ieșire din matricea de intrare, unde n este lungimea curentă a matricei de intrare. După copierea n elemente de la intrare, putem efectua n operații dequeue, fiecare luând timp constant, înainte ca matricea de ieșire să fie din nou goală. Astfel, putem efectua o secvență de n operații dequeue numai în O ( n ) {\displaystyle o(n)}
timp, ceea ce implică faptul că timpul amortizat al fiecărei operații dequeue este O ( 1 ) {\displaystyle o(1)}
