Dinamico arrayEdit
si Consideri un array dinamico che cresce in dimensioni più elementi vengono aggiunti, ad esempio ArrayList in Java o std::vector in C++. Se abbiamo iniziato con un array dinamico di dimensione 4, potremmo spingere 4 elementi su di esso, e ogni operazione richiederebbe tempo costante. Tuttavia, spingere un quinto elemento su quell’array richiederebbe più tempo in quanto l’array dovrebbe creare un nuovo array di dimensioni doppie rispetto alla dimensione corrente (8), copiare i vecchi elementi sul nuovo array e quindi aggiungere il nuovo elemento. Le successive tre operazioni di push richiederebbero allo stesso modo un tempo costante, e quindi l’aggiunta successiva richiederebbe un altro raddoppio lento della dimensione dell’array.
In generale, se consideriamo un numero arbitrario di push n + 1 a un array di dimensioni n, notiamo che le operazioni di push richiedono tempo costante tranne che per l’ultimo che richiede Θ ( n ) {\displaystyle \Theta (n)}
tempo per eseguire l’operazione di raddoppio delle dimensioni. Poiché c’erano n + 1 operazioni totali possiamo prendere la media di questo e scoprire che spingere gli elementi sull’array dinamico richiede: n Θ ( 1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, costante di tempo.
QueueEdit
Shown is a Ruby implementation of a Queue, a FIFO data structure:
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
L’operazione enqueue spinge solo un elemento sull’array di input; questa operazione non dipende dalla lunghezza di input o output e quindi viene eseguita in tempo costante.
Tuttavia l’operazione di dequeue è più complicata. Se l’array di output contiene già alcuni elementi, dequeue viene eseguito in tempo costante; altrimenti, dequeue richiede O ( n ) {\displaystyle O(n)}
tempo per aggiungere tutti gli elementi all’array di output dall’array di input, dove n è la lunghezza corrente dell’array di input. Dopo aver copiato n elementi dall’input, possiamo eseguire n operazioni di dequeue, ciascuna delle quali richiede tempo costante, prima che l’array di output sia nuovamente vuoto. Pertanto, possiamo eseguire una sequenza di n operazioni di dequeue solo in O ( n ) {\displaystyle O(n)}
tempo, il che implica che il tempo ammortizzato di ogni operazione di dequeue è O ( 1 ) {\displaystyle O(1)}
