Dinâmica arrayEdit
Considere uma matriz dinâmica, que cresce em tamanho quanto mais elementos são adicionados a ele, como ArrayList em Java ou std::vector em C++. Se começássemos com uma matriz dinâmica de tamanho 4, poderíamos colocar 4 elementos nela, e cada operação levaria tempo constante. Ainda assim, empurrar um quinto elemento para esse array levaria mais tempo, pois o array teria que criar um novo array com o dobro do tamanho atual (8), copiar os elementos antigos para o novo array, e então adicionar o novo elemento. As três operações de push seguintes teriam igualmente um tempo constante, e então a adição subsequente exigiria outra duplicação lenta do tamanho do array.
Em geral, se considerarmos um número arbitrário de empurra n + 1 para uma matriz de tamanho n, notamos que empurrar operações de constante de tempo, exceto a última, que leva Θ ( n ) {\displaystyle \Theta (n)}
tempo para realizar o tamanho dobrando a operação. Uma vez que havia n + 1 Total de operações podemos pegar a média disto e descobrir que empurrar elementos para a matriz dinâmica leva: n Θ ( 1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, constante de tempo.
QueueEdit
Mostrado é um Ruby implementação de uma Fila FIFO estrutura de dados:
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
A operação enqueue apenas empurra um elemento para a matriz de entrada; esta operação não depende do comprimento de entrada ou de saída e, portanto, é executado em tempo constante.
no entanto, a operação dequeue é mais complicada. Se a matriz de saída já tem alguns elementos, então a fila é executado em tempo constante; caso contrário, dequeue leva O ( n ) {\displaystyle S(n)}
hora de adicionar todos os elementos na matriz de saída da matriz de entrada, onde n é o comprimento atual da matriz de entrada. Depois de copiar n elementos de entrada, podemos executar n dequeue operações, cada uma tomando tempo constante, antes que a matriz de saída esteja vazia novamente. Assim, podemos realizar uma sequência de n dequeue operações em apenas O ( n ) {\displaystyle S(n)}
tempo, o que implica que a amortizado de cada operação dequeue é O ( 1 ) {\displaystyle O(1)}
