Tiempo Amortizado Constante

Question

¿Qué se entiende por " Constant Amortized Time " Cuando se habla de la complejidad del tiempo de un algoritmo?

Answer 1

Tiempo amortizado explicado en términos simples:

Si realiza una operación un millón de veces, realmente no le importa el peor de los casos ni el mejor de ellos: lo que le importa es cuánto tiempo se tarda en total cuando repite 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 " Es lo suficientemente raro como para que la lentitud se diluya. El tiempo esencialmente amortizado significa "tiempo promedio tomado por operación, si realiza muchas operaciones". El tiempo amortizado no tiene que ser constante; puede tener un tiempo amortizado lineal y logarítmico o cualquier otra cosa.

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

Entonces, cada vez que amplías, te tomas 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 puede, por lo tanto, " repartirse " Entre las inserciones. Esto significa que, a largo plazo, el tiempo total necesario para agregar elementos m a la matriz es O (m) , y por lo tanto el tiempo amortizado (es decir, el tiempo por inserción) es O (1) .

Answer 2

Significa que, con el tiempo, el peor de los casos se establecerá de forma predeterminada en O (1), o tiempo constante. Un ejemplo común es la matriz dinámica. Si ya hemos asignado memoria para una nueva entrada, la adición será O (1). Si no lo hemos asignado, lo haremos asignando, por ejemplo, el doble del monto actual. Esta inserción en particular no será O (1), sino algo más.

Lo importante es que el algoritmo garantiza que después de una secuencia de operaciones, las operaciones costosas se amortizarán y, por lo tanto, la operación completa 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 & # 322; Dowgird )

Answer 3

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

Las partes verticales del gráfico negro corresponden a reasignaciones de memoria para expandir una matriz. 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 las operaciones de C * N en promedio para agregar N elementos a la matriz, o las operaciones de C * 1 para agregar un elemento (tiempo constante amortizado) .

Answer 4

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

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

  

" Dynamic Array

     

Análisis amortizado de la operación de inserción para una matriz dinámica

     

Considere una matriz dinámica que crece de tamaño a medida que se le agregan más elementos   como un ArrayList en Java. Si empezamos con una matriz dinámica.   de tamaño 4, llevaría tiempo constante empujar cuatro elementos sobre él.   Sin embargo, empujar un quinto elemento en esa matriz llevaría más tiempo que el   La matriz tendría que crear una nueva matriz del doble del tamaño actual (8),   copie los elementos antiguos en la nueva matriz y luego agregue la nueva   elemento. Las siguientes tres operaciones de empuje serían igualmente constantes.   tiempo, y luego la adición posterior requeriría otra lenta   duplicación del tamaño de la matriz.

     

En general, si consideramos un número arbitrario de empujes n a una matriz   de tamaño n, notamos que las operaciones de empuje toman tiempo constante, excepto   para el último que lleva O (n) tiempo para realizar el doble de tamaño   operación. Como hubo n operaciones totales podemos tomar el promedio   de esto y encontrar que para empujar elementos en la matriz dinámica   toma: O (n / n) = O (1), tiempo constante. "

A mi entender como una historia simple:

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

Entonces, ve directo al final / esquina de la habitación y comienza a apilarlos. A medida que los apiles, lentamente la habitación se quedará sin espacio. Sin embargo, a medida que rellenas fue fácil apilarlos. Conseguí 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 sea más grande. Aquí hay un problema, ya que solo podemos tener 1 habitación, así que solo podemos tener 1 cerradura, necesitamos mover todo el dinero existente en esa habitación a la nueva habitación más grande. Entonces, mueva todo el dinero, desde una habitación pequeña a una habitación más grande. Es decir, apilar todos de nuevo. Por lo tanto, necesitamos mover todo el dinero anterior. Por lo tanto, es O (N). (Suponiendo que N es el recuento total de dinero del dinero anterior)

En otras palabras, fue fácil hasta N, solo 1 operación, pero cuando necesitamos mudarnos a una habitación más grande, hicimos N operaciones. Entonces, en otras palabras, si promediamos, es 1 inserto al comienzo y 1 movimiento más al mudarnos a otra habitación. Total de 2 operaciones, una inserción, un movimiento.

Suponiendo que N es grande como 1 millón incluso en la sala 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).

Suponiendo que hacemos todo lo anterior en otra habitación más grande, y de nuevo necesitamos movernos. Sigue siendo el mismo. por ejemplo, N2 (por ejemplo, 1 billón) es una nueva cantidad de dinero en la sala más grande

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

Todavía necesitamos solo 2 operaciones, una se inserta en una habitación más grande, luego otra operación de movimiento para moverse a una habitación aún más grande.

Entonces, incluso para N2 (1 billón), son 2 operaciones para cada una. que no es nada de nuevo. Por lo tanto, es constante, o O (1)

Entonces, a medida que la N aumenta de N a N2, u otra, no importa mucho. Sigue siendo constante, o operaciones O (1) requeridas para cada una de las N.

---

Supongamos que tiene N como 1, muy pequeño, la cantidad de dinero es pequeña y que tiene una habitación muy pequeña, que se ajustará a solo 1 cuenta de dinero.

Tan pronto como llenes el dinero en la sala, la sala se llena.

Cuando vaya a la sala más grande, suponga que solo puede caber un dinero más, un total de 2 cargos de dinero. Eso significa que, el anterior movió dinero y 1 más. Y de nuevo se llena.

De esta manera, la N está creciendo lentamente y ya no es más constante O (1), ya que estamos moviendo todo el dinero de la sala anterior, pero solo podemos colocar 1 dinero más.

Después de 100 veces, la nueva sala tiene capacidad para 100 cuentas del dinero anterior y 1 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, millones de millones y miles de millones. .

Por lo tanto, esta es una forma ineficiente de asignar salas (o memoria / RAM) para nuestro dinero (variables).

---

Por lo tanto, una buena manera es asignar más espacio, con poderes de 2.

Tamaño de la primera habitación = se adapta a 1 cargo de dinero
Tamaño de la segunda habitación = cabe 4 cuentas de dinero
Tamaño de la tercera habitación = se ajusta a 8 cuentas de dinero
Tamaño de la cuarta habitación = se ajusta a 16 cuentas de dinero
Tamaño de la 5ta habitación = se ajusta a 32 cuentas de dinero
Tamaño de la sexta habitación = se ajusta a 64 cuentas de dinero
Tamaño de la séptima habitación = se ajusta a 128 cuentas de dinero
Tamaño de la octava habitación = cabe 256 cuentas de dinero
Tamaño de la 9ª habitación = cabe 512 conteo de dinero
Tamaño de la 10ª habitación = se ajusta a 1024 recuento de dinero
Tamaño de la 11ª habitación = se ajusta a 2,048 conteo de dinero
...
Tamaño de la habitación 16 = se ajusta a 65,536 conteo 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 después, 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 por dinero es fija (2) y no es comparable con el tamaño de la habitación (N), la habitación que tomamos en las etapas iniciales Es posible que sea demasiado grande (1 millón) y no lo utilicemos en su totalidad, dependiendo de si podemos obtener tanto dinero para ahorrar en el primer caso.

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

Answer 5

Las explicaciones anteriores se aplican al Análisis Agregado, la idea de tomar " un promedio " sobre múltiples operaciones. No estoy seguro de cómo se aplican al método de banqueros o al método de análisis físico amortizado.

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

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

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

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

Dado que tenemos el caso de que algunas operaciones están sobrecargadas, mientras que otras operaciones están infrautilizadas, una hipótesis podría ser que no tendría sentido cotizar los costos amortizados de las operaciones individuales.

Por ejemplo: para un montón de Fibonacci, no tiene sentido citar el costo amortizado de solo la tecla de disminución para ser O (1) ya que los costos se reducen por el trabajo realizado por las operaciones anteriores en un potencial creciente del montón. "

O

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

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

2. Por el bien del análisis, voy a cobrar de más algunas operaciones de bajo costo, POR LO TANTO QUE SU COSTO ASÍPTOTICO NO CAMBIA.

3. Con estas operaciones de bajo costo incrementado, puedo demostrar que una operación costosa tiene un COSTO ASIMPÓTICO MÁS PEQUEÑO.

4. Por lo tanto, he mejorado / disminuido el ASIMPÓTICO-LIMITADO del costo de n operaciones.

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