Tiempo constante amortizado

¿Qué se entiende por “tiempo constante amortizado” cuando se habla de la complejidad temporal de un algoritmo?

Tiempo amortizado explicado en términos simples:

Si haces una operación, por ejemplo, un millón de veces, realmente no te importa el peor de los casos o el mejor caso de esa operación: lo que te importa es cuánto tiempo se tarda en total cuando repites la operación un millón de veces .

Por lo tanto, no importa si la operación es muy lenta de vez en cuando, siempre que “de vez en cuando” sea lo suficientemente raro como para diluir la lentitud. Tiempo esencialmente amortizado significa “tiempo promedio tomado por operación, si realiza muchas operaciones”. El tiempo amortizado no tiene que ser constante; puede tener tiempo amortizado lineal y logarítmico o cualquier otra cosa.

Tomemos el ejemplo de esteras de una matriz dinámica, a la que agrega repetidamente nuevos elementos. Normalmente, agregar un elemento lleva tiempo constante (es decir, O(1) ). Pero cada vez que la matriz está llena, se asigna el doble de espacio, se copian los datos en la nueva región y se libera el espacio anterior. Suponiendo que asigna y libera ejecución en tiempo constante, este proceso de ampliación toma O(n) tiempo donde n es el tamaño actual de la matriz.

Por lo tanto, cada vez que se agranda, toma aproximadamente el doble de tiempo que la última ampliación. ¡Pero también has esperado el doble de tiempo antes de hacerlo! El costo de cada ampliación se puede “extender” entre las inserciones. Esto significa que, a largo plazo, el tiempo total necesario para agregar m elementos al conjunto es O(m) , por lo que el tiempo amortizado (es decir, el tiempo por inserción) es O(1) .

Significa que con el tiempo, el peor de los escenarios tendrá como valor predeterminado O (1) o tiempo constante. Un ejemplo común es la matriz dinámica. Si ya hemos asignado memoria para una nueva entrada, agregarla será O (1). Si no lo hemos asignado, lo haremos asignando, por ejemplo, el doble de la cantidad actual. Esta inserción particular no será O (1), sino algo más.

Lo que es importante es que el algoritmo garantiza que después de una secuencia de operaciones, las costosas operaciones se amortizarán y, por lo tanto, representarán toda la operación O (1).

O en términos más estrictos,

Hay una constante c, tal que para cada secuencia de operaciones (también una que termina con una operación costosa) de longitud L, el tiempo no es mayor que c * L (gracias Rafał Dowgird )

Para desarrollar una forma intuitiva de pensar al respecto, considere la inserción de elementos en una matriz dinámica (por ejemplo, std::vector en C ++). Vamos a trazar un gráfico, que muestra la dependencia del número de operaciones (Y) necesarias para insertar N elementos en la matriz:

trama

Las partes verticales del gráfico negro corresponden a reasignaciones de memoria para expandir un conjunto. Aquí podemos ver que esta dependencia se puede representar aproximadamente como una línea. Y esta ecuación de línea es Y=C*N + b ( C es constante, b = 0 en nuestro caso). Por lo tanto, podemos decir que necesitamos gastar C*N operaciones en promedio para agregar N elementos a la matriz, o C*1 operaciones para agregar un elemento (tiempo constante amortizado).

A continuación, encontré útil la explicación de Wikipedia, luego de repetir la lectura 3 veces:

Fuente: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

“Matriz dinámica

Análisis Amortizado de la operación Push para una matriz dinámica

Considere una matriz dinámica que crece en tamaño a medida que se le agregan más elementos, como ArrayList en Java. Si comenzáramos con una matriz dinámica de tamaño 4, tomaría un tiempo constante insertar cuatro elementos en ella. Sin embargo, presionar un quinto elemento en 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 inserción tomarían de manera similar 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 impulsos n en una matriz de tamaño n, notamos que las operaciones de inserción toman tiempo constante, excepto en el último, que toma O (n) tiempo para realizar la operación de duplicación de tamaño. Dado que hubo n operaciones totales, podemos tomar el promedio de esto y encontrar que para empujar elementos en la matriz dinámica se necesita: O (n / n) = O (1), tiempo constante “.

A mi entender, como una historia simple:

Suponga que tiene mucho dinero. Y, quieres astackrlos en una habitación. Y, tienes manos y piernas largas, tanto tiempo como lo necesites ahora o en el futuro. Y, tiene que llenar todo en una habitación, por lo que es fácil bloquearlo.

Entonces, vas directamente al extremo / esquina de la sala y comienzas a astackrlos. Mientras los astack, lentamente la habitación se quedará sin espacio. Sin embargo, al llenarlo fue fácil astackrlos. Tengo el dinero, pon el dinero. Fácil. Es O (1). No necesitamos mover ningún dinero anterior.

Una vez que la habitación se queda sin espacio. Necesitamos otra habitación, que es más grande. Aquí hay un problema, ya que solo podemos tener 1 habitación, por lo que solo podemos tener 1 cerradura, tenemos que mover todo el dinero existente en esa habitación a la sala más grande. Por lo tanto, mueva todo el dinero, desde una habitación pequeña a una habitación más grande. Es decir, astackr todos ellos de nuevo. Entonces, NECESITAMOS mover todo el dinero anterior. Entonces, es O (N). (suponiendo que N es el conteo total de dinero del dinero anterior)

En otras palabras, fue fácil hasta N, solo 1 operación, pero cuando necesitamos movernos a una habitación más grande, hicimos N operaciones. Entonces, en otras palabras, si hacemos un promedio, es 1 inserción en el inicio, y 1 movimiento más mientras se mueve a otra sala. Total de 2 operaciones, una inserción, un movimiento.

Suponiendo que N es grande como 1 millón incluso en la habitación pequeña, las 2 operaciones comparadas con N (1 millón) no son realmente un número comparable, por lo que se considera constante o O (1).

Asumiendo cuando hacemos todo lo anterior en otra habitación más grande, y nuevamente tenemos que movernos. Sigue siendo el mismo digamos, N2 (digamos, 1 billón) es una nueva cantidad de conteo de dinero en la sala más grande

Por lo tanto, tenemos N2 (que incluye N de la anterior, ya que nos movemos todos de la habitación pequeña a la más grande)

Todavía necesitamos solo 2 operaciones, una es insertarla en una habitación más grande, y luego otra operación mover para moverla a una habitación aún más grande.

Entonces, incluso para N2 (mil millones), son 2 operaciones para cada uno. que no es nada más Entonces, es constante, o O (1)

Entonces, cuando el N aumenta de N a N2, u otro, no importa mucho. Todavía es constante, o O (1) operaciones requeridas para cada uno de los N.


Ahora suponga que tiene N como 1, muy pequeño, el recuento de dinero es pequeño y tiene una habitación muy pequeña, que solo tendrá 1 cargo de dinero.

Tan pronto como llene el dinero en la habitación, la habitación se llena.

Cuando vaya a la sala más grande, suponga que solo puede caber un dinero más, total de 2 cuentas de dinero. Eso significa que el dinero movido anterior y 1 más. Y de nuevo está lleno.

De esta forma, el N está creciendo lentamente, y no es más constante O (1), ya que estamos moviendo todo el dinero de la habitación anterior, pero solo puede caber 1 dinero más.

Después de 100 veces, la nueva sala se ajusta a 100 cuentas de dinero de anteriores y 1 dinero más que puede acomodar. Esto es O (N), ya que O (N + 1) es O (N), es decir, el grado de 100 o 101 es el mismo, ambos son cientos, a diferencia de la historia anterior, de uno a millones y de uno a miles de millones .

Entonces, esta es una manera ineficiente de asignar salas (o memoria / RAM) para nuestro dinero (variables).


Entonces, una buena manera es asignar más espacio, con poderes de 2.

1er tamaño de habitación = se ajusta a 1 conteo de dinero
2. ° tamaño de la habitación = se adapta a 4 recuentos de dinero
3er tamaño de habitación = se adapta a 8 cargos de dinero
Cuarto tamaño de la habitación = se ajusta a 16 cuentas de dinero
5to tamaño de habitación = se ajusta a 32 cuentas de dinero
6to tamaño de habitación = cabe 64 conteos de dinero
7mo tamaño de habitación = cabe 128 conteos de dinero
8º tamaño de habitación = cabe 256 cuentas de dinero
9º tamaño de habitación = se ajusta a 512 cuentas de dinero
10mo tamaño de habitación = se ajusta a 1024 conteos de dinero
Tamaño de la habitación 11 = se ajusta a 2.048 recuento de dinero

Tamaño de la habitación 16 = se ajusta a 65,536 conteos de dinero

Tamaño de la habitación 32 = se ajusta a 4,294,967,296 conteo de dinero

Tamaño de la habitación 64 = se ajusta a 18,446,744,073,709,551,616 conteo de dinero

¿Por qué es esto mejor? Porque parece crecer lentamente al principio, y más rápido más tarde, es decir, en comparación con la cantidad de memoria en nuestra memoria RAM.

Esto es útil porque, en el primer caso, aunque es bueno, la cantidad total de trabajo que se debe hacer por dinero es fija (2) y no comparable con el tamaño de la sala (N), la sala que tomamos en las etapas iniciales también podría ser grande (1 millón) que no podemos utilizar por completo, dependiendo de si es posible que ganemos ese dinero en primer lugar.

Sin embargo, en el último caso, potencias de 2, crece en los límites de nuestra memoria RAM. Y así, al boost en potencias de 2, tanto el análisis armotizado permanece constante y es amigable para la memoria RAM limitada que tenemos hasta el día de hoy.

Las explicaciones anteriores se aplican a Aggregate Analysis, la idea de tomar “un promedio” sobre múltiples operaciones. No estoy seguro de cómo se aplican a Bankers-method o Physicists Methods of Amortized analysis.

Ahora. No estoy exactamente seguro de la respuesta correcta. Pero tendría que ver con la condición principal de ambos métodos de Físicos + Banquero:

(Suma del costo amortizado de las operaciones)> = (Suma del costo real de las operaciones).

La dificultad principal a la que me enfrento es que dado que los costos de operación Amortizados-asintóticos difieren del costo asintótico normal, no estoy seguro de cómo calificar la importancia de los costos amortizados.

Es entonces cuando alguien me da un costo amortizado, sé que no es lo mismo que un costo asintótico normal. ¿Qué conclusiones debo extraer del costo amortizado?

Dado que tenemos el caso de que algunas operaciones se cobraron de más, mientras que otras operaciones no se cobraron, una hipótesis podría ser que citar los costos amortizados de las operaciones individuales no tendría sentido.

Por ejemplo: para un montón de fibonacci, citar el costo amortizado de Just Decreasing-Key para ser O (1) no tiene sentido ya que los costos se reducen por “el trabajo realizado por operaciones anteriores para boost el potencial del montón”.

O

Podríamos tener otra hipótesis que razone sobre los costos amortizados de la siguiente manera:

  1. Sé que la costosa operación va a ir precedida de operaciones MÚLTIPLES DE BAJO COSTO.

  2. Por el bien del análisis, voy a cobrar de más algunas operaciones de bajo costo, TALES QUE SUS COSTOS ASINTÉTICOS NO CAMBIAN.

  3. Con estas operaciones de bajo costo aumentadas, PUEDO PROBAR QUE UNA OPERACIÓN CARO tiene un COSTO ASINTÓTICO MÁS PEQUEÑO.

  4. Por lo tanto, he mejorado / disminuido el LÍMITE ASINTÓTICO del costo de n operaciones.

Por lo tanto, el análisis del costo amortizado + límites de costo amortizado ahora se aplica solo a las costosas operaciones. Las operaciones baratas tienen el mismo costo amortizado asintótico que su costo asintótico normal.