Tiempo amortizado constante

Question

¿Qué se entiende por "Tiempo amortizado constante" cuando se habla de la complejidad temporal de un algoritmo?

Answer 1

tiempo amortizado explica en términos sencillos:

Si realiza una operación, digamos un millón de veces, realmente no le importa el peor de los casos o el mejor de esa operación; lo que le importa es cuánto tiempo se tarda en total cuando repite la operación un millón veces.

Así que 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.

Así que 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 a la matriz es O(m), por lo que el tiempo amortizado (es decir, el tiempo por inserción) es O(1).

Answer 2

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 será no sea 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 de ese modo se realizará 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 uno que termina con una operación costosa) de longitud L, el tiempo no es mayor que c * L (Gracias Rafał Dowgird)

Answer 3

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 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-asintóticos difieren del costo asintótico normal, no estoy seguro de cómo calificar la importancia de los costos amortizados.

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

Dado que tenemos el caso de algunas operaciones que se cobran de más, mientras que otras operaciones no están cargadas, 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, citando el costo amortizado de Just Decreasing-Key ser O (1) no tiene sentido ya que los costos se reducen por "trabajo realizado por operaciones anteriores para aumentar el potencial del montón".

O

Podríamos tener otra hipótesis de que las razones sobre-costos amortizados de la siguiente manera:

1. Sé que la operación costosa va a precedida por operaciones de bajo costo MÚLTIPLES.

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

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

4. Por lo tanto, he mejorado/reducido el ASINTAMIENTO-LÍMITE del costo de n operaciones.

Por lo tanto, el análisis de costo-amortizado + costo-límite-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.

Answer 4

me encontré debajo Wikipedia explicación útil, después repita la lectura por 3 veces:

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

"matriz dinámica

Análisis de amortización de la operación de empuje 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ó con un arreglo dinámico de tamaño 4, tomaría tiempo constante insertar cuatro elementos en él. 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 el tiempo constante, y luego la adición posterior requeriría otra duplicación lenta de doblando el tamaño de la matriz.

En general, si consideramos un número arbitrario de empujes n a una matriz de tamaño n, nos damos cuenta de que las operaciones de empuje toman tiempo constante, excepto para la última que toma tiempo O (n) para llevar a cabo el tamaño duplicar operación. Puesto que no había n total de operaciones podemos tomar el promedio de esto y encontrar que para empujar los elementos en la matriz dinámica toma: O (n/n) = O (1), la constante de tiempo "

Para. Tengo entendido como una historia sencilla:

Suponga que tiene un montón de dinero y, desea apilarlos en una habitación y, usted tiene largas manos y las piernas, tanto el tiempo que necesite ahora o.. en el futuro. Y, tiene que llenar todo en una habitación, por lo que es fácil de bloquearlo.

Entonces, vas directamente al extremo/esquina de la sala y comienzas a apilarlos. Mientras los apila, lentamente la habitación se quedará sin espacio. Sin embargo, cuando lo llene, fue fácil apilarlos. 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. Así que mueva todo el dinero, desde una habitación pequeña a una habitación más grande. Es decir, apilar todos ellos de nuevo. Entonces, NECESITAMOS mover todo el dinero anterior. Entonces, 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 tenemos que movernos a una sala 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).

Suponiendo que hagamos todo lo anterior en otra sala más grande, y nuevamente tengamos que movernos. Sigue siendo el mismo. decir, N2 (por ejemplo, 1 mil millones) es nueva cantidad de recuento de dinero en la habitación más grande

Por lo tanto, tenemos N2 (que incluye N de la anterior, ya que nos movemos todos de pequeño a habitación 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.

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

Por lo tanto, como 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.

---

Supongamos ahora, que tiene como N 1, muy pequeño, el recuento de dinero es pequeña, y tiene una habitación muy pequeña, que sólo puede acoplarse a 1 recuento de dinero.

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

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 manera, la 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 caben 1 dinero más.

Después de 100 veces, la nueva sala se ajusta a 100 monedas de dinero de la anterior 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 .

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

---

Por lo tanto, una buena manera es la asignación de más espacio, con potencias de 2.

tamaño primera habitación = 1 se ajusta el recuento de dinero
tamaño segunda sala se ajusta = 4 recuento de dinero
tercera habitación size = 8 encaja recuento de dinero
tamaño cuarto de estar = 16 encaja recuento de dinero
tamaño quinto de estar = 32 encaja recuento de dinero
tamaño de la habitación sexta = 64 encaja recuento de dinero
séptima habitación size = encaja 128 recuento de dinero
tamaño de la habitación octava = encaja 256 recuento de dinero
tamaño de la habitación noveno = encaja 512 recuento de dinero
tamaño de la habitación 10a = encaja de 1024 cuentas de dinero
tamaño de la habitación 11 = encaja 2.048 recuento de dinero
...
tamaño de la habitación 16a encaja = 65.536 recuento de dinero
...
tamaño de la habitación 32th encaja = 4294967296 recuento de dinero
...
tamaño de la habitación 64a = encaja 18,446,744,073,709,551,616 recuento 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 por dinero es fija (2) y no comparable al tamaño de la habitación (N), la habitación que tomamos en la inicial las etapas pueden ser demasiado grandes (1 millón) que puede que no usemos 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 aumentar 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.

Answer 5

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

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