algorithm - little - big o rapper
Tiempo Amortizado Constante (5)
¿Qué se entiende por "Tiempo Amortizado Constante" cuando se habla de la complejidad del tiempo de un algoritmo?
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
"Array dinámico
Análisis amortizado de la operación de empuje 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 comenzáramos con una matriz dinámica de tamaño 4, llevaría tiempo constante empujar cuatro elementos en ella. Sin embargo, empujar un quinto elemento en esa matriz tomarí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án un tiempo constante de manera similar, y luego la adición subsiguiente requerirá otra duplicación lenta del tamaño del arreglo.
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 un tiempo constante, excepto el último que toma O (n) tiempo para realizar la operación de duplicación de tamaño. Como hubo un total de n operaciones, podemos tomar el promedio de esto y encontrar que, para insertar elementos en la matriz dinámica, se toma: O (n / n) = O (1), tiempo constante ".
A mi entender como una simple historia:
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 podemos tener solo 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, apilarlos 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 en comparación con N (1 millón) no son realmente un número comparable, por lo que se considera constante u 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 lo anterior, ya que todos nos movemos de una habitación pequeña a una más grande)
Todavía necesitamos solo 2 operaciones, una para insertar en una habitación más grande, y luego otra para mover a una habitación aún más grande.
Entonces, incluso para N2 (1 billón), son 2 operaciones para cada uno. 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.
Ahora suponga que tiene N como 1, muy pequeño, la cantidad de dinero es pequeña, y tiene una habitación muy pequeña, que se ajustará a solo 1 cuenta de dinero.
Tan pronto como llenes 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 en ella, 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 se ajusta a 100 cargos del dinero 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, 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).
Entonces, una buena manera es asignar más espacio, con poderes de 2.
Tamaño de la primera habitación = se ajusta a 1 cuenta de dinero
Tamaño de la segunda habitación = se ajusta a 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 = cabe 1024 conteo de dinero
Tamaño de la sala 11 = se ajusta a 2.048 cuenta 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 a realizar por dinero es fija (2) y no es comparable al tamaño de la habitación (N), la sala que tomamos en las etapas iniciales podría ser demasiado grande (1 millón) que puede que no usemos totalmente 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 armotizado se mantiene constante y es amigable para la memoria RAM limitada que tenemos hoy en día.
Esto 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 caras se amortizarán y, por lo tanto, se traducirá en toda la operación O (1).
O en términos más estrictos,
Hay una constante c, de modo 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 )
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 los Banqueros o los Métodos de Análisis Amortizados de los Físicos.
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 las operaciones Amortizadas y asintóticas difieren de los costos normales y asintóticos, no estoy seguro de cómo calificar la importancia de los costos amortizados.
Entonces, 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 entonces?
Dado que tenemos el caso de que algunas operaciones se cobran en exceso, mientras que otras operaciones tienen un bajo costo, una hipótesis podría ser que no tendría sentido citar 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:
Sé que la operación costosa va a ser precedida por operaciones MÚLTIPLES DE BAJO COSTO.
Por el bien del análisis, voy a sobrecargar algunas operaciones de bajo costo, TALES QUE EL COSTO ASÍPTOTICO NO CAMBIA.
Con estas operaciones de bajo costo incrementado, puedo PROBAR QUE UNA OPERACIÓN EXPENSIVA tenga un COSTO ASÍPTOTICO MÁS PEQUEÑO.
Por lo tanto, he mejorado / disminuido el límite ASÍPTOTICO del costo de n operaciones.
Por lo tanto, el análisis del costo amortizado + los límites del costo amortizado ahora se aplican solo a las operaciones costosas. Las operaciones baratas tienen el mismo costo asintótico-amortizado que su costo normal-asintótico.
Para desarrollar una forma intuitiva de pensar en ello, 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:
Las partes verticales del gráfico negro corresponden a las 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 debemos 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).
Tiempo amortizado explicado en términos simples:
Si realiza una operación, digamos un millón de veces, realmente no le importa el peor de los casos o el mejor de ellos: lo que le importa es cuánto tiempo se tarda en total cuando se repite la operación un millón de veces .
Así que no importa si la operación es muy lenta de vez en cuando, siempre y cuando "de vez en cuando" sea 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 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, agregar 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 lleva un tiempo O(n) donde n es el tamaño actual de la matriz.
Así que 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 se puede "repartir" entre las inserciones. Esto significa que a largo plazo, el tiempo total que se tarda en 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) .