arrayEdit dinámico
Considere un array dinámico que crece en tamaño a medida que se agregan más elementos, como ArrayList en Java o std::vector en C++. Si empezamos con una matriz dinámica de tamaño 4, podríamos empujar 4 elementos en ella, y cada operación tomaría un tiempo constante. Sin embargo, empujar un quinto elemento a esa matriz llevaría más tiempo, ya que la matriz tendría que crear una nueva matriz del doble del tamaño actual (8), copiar los elementos antiguos en la nueva matriz y luego agregar el nuevo elemento. Las siguientes tres operaciones de empuje tomarían de manera similar un tiempo constante, y luego la adición posterior requeriría otra duplicación lenta del tamaño de la matriz.
En general, si consideramos un número arbitrario de empujes n + 1 a una matriz de tamaño n, notamos que las operaciones de empuje toman tiempo constante, excepto para la última que toma Θ ( n ) {\displaystyle \Theta (n)}
tiempo para realizar la operación de duplicación de tamaño. Dado que hubo un total de operaciones n + 1, podemos tomar el promedio de esto y encontrar que los elementos empujados en el array dinámico toman: n Θ ( 1 ) + Q ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
tiempo constante.
QueueEdit
Se muestra una implementación Ruby de una Cola, una estructura de datos 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
La operación enqueue simplemente empuja un elemento al array de entrada; esta operación no depende de la longitud de entrada o salida y, por lo tanto, se ejecuta en tiempo constante.
Sin embargo, la operación de desagüe es más complicada. Si la matriz de salida ya tiene algunos elementos, entonces dequeue se ejecuta en tiempo constante; de lo contrario, dequeue toma O ( n ) {\displaystyle O(n)}
tiempo para agregar todos los elementos a la matriz de salida desde la matriz de entrada, donde n es la longitud actual de la matriz de entrada. Después de copiar n elementos de entrada, podemos realizar n operaciones de desqueue, cada una tomando tiempo constante, antes de que la matriz de salida esté vacía de nuevo. Por lo tanto, podemos realizar una secuencia de n operaciones de desagüe en solo O(n ) {\displaystyle O(n)}
tiempo, lo que implica que el tiempo amortizado de cada operación de desagüe es O ( 1 ) {\displaystyle O(1)}
