¿Qué es el análisis amortizado de algoritmos? [cerrado]

¿En qué se diferencia del análisis asintótico? ¿Cuándo lo usa y por qué?

He leído algunos artículos que parecen estar bien escritos, como estos:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

pero todavía no he entendido completamente estos conceptos.

Entonces, ¿alguien puede simplificarme por favor?

El análisis amortizado no multiplica ingenuamente el número de invocaciones con el peor de los casos para una invocación.

Por ejemplo, para una matriz dinámica que duplica su tamaño cuando es necesario, el análisis asintótico normal solo concluiría que agregarle un elemento cuesta O (n), porque podría necesitar crecer y copiar todos los elementos a la nueva matriz. El análisis amortizado toma en cuenta que para tener que crecer, se deben haber agregado n / 2 artículos sin causar un crecimiento desde el crecimiento anterior, por lo que agregar un artículo realmente solo toma O (1) (el costo de O (n) es amortizado en n / 2 acciones).

El análisis amortizado no es lo mismo que un "rendimiento promedio": el análisis amortizado ofrece una garantía sólida de lo que hará el rendimiento si realiza tantas acciones.

Hay muchas respuestas al "qué", pero ninguna al "por qué".

Como todos los demás han dicho, el análisis asintótico trata sobre cómo el rendimiento de una operación determinada se escala a un gran conjunto de datos. El análisis amortizado se trata de cómo se escala el promedio del rendimiento de todas las operaciones en un gran conjunto de datos. El análisis amortizado nunca da peores límites que los asintóticos y, a veces, ofrece límites mucho mejores.

Si le preocupa el tiempo total de ejecución de un trabajo más largo, probablemente lo que le interese sean los mejores límites del análisis amortizado. Es por eso que los lenguajes de scripting (por ejemplo) a menudo están felices de aumentar las matrices y las tablas hash en algún factor, aunque esa es una operación costosa. (El cultivo puede ser una O(n)operación, pero se amortiza O(1)porque rara vez lo haces).

Si está haciendo programación en tiempo real (las operaciones individuales deben completarse en un tiempo predecible), entonces los mejores límites del análisis amortizado no importan. No importa si la operación en promedio fue rápida, si no pudo terminarla a tiempo para regresar y ajustar la sierra de cinta antes de que cortara demasiado ...

Cuál importa en su caso depende exactamente de cuál sea su problema de programación.

Análisis asintótico

Este término se refiere al análisis del rendimiento del algoritmo bajo el supuesto de que los datos sobre los que opera el algoritmo (la entrada ) son, en términos sencillos, "lo suficientemente grandes como para que hacerlo más grande no cambie la conclusión". Aunque no es necesario especificar el tamaño exacto de la entrada (solo necesitamos un límite superior), el conjunto de datos en sí tiene debe especificar .

Tenga en cuenta que hasta ahora solo hemos hablado del método de análisis; no hemos especificado exactamente qué cantidad estamos analizando (¿complejidad del tiempo? ¿complejidad del espacio?), y tampoco hemos especificado qué métrica nos interesa (¿en el peor de los casos, en el mejor de los casos, en el promedio?).

En la práctica, el término análisis asintótico se refiere comúnmente a la complejidad de tiempo límite superior de un algoritmo, es decir, el peor desempeño del caso medido por el tiempo de ejecución total, que está representado por la notación de gran Oh (por ejemplo, un algoritmo de clasificación podría serlo O(nlogn)).

Análisis amortizado

Este término se refiere al análisis del rendimiento del algoritmo basado en una secuencia específica de operaciones que tiene como objetivo el peor de los casos , es decir, el análisis amortizado implica que la métrica es el peor rendimiento del caso (aunque todavía no dice qué cantidad se está midiendo ). Para realizar este análisis, necesitamos especificar el tamaño de la entrada, pero no necesitamos hacer suposiciones sobre su forma.

En términos sencillos, el análisis amortizado es elegir un tamaño arbitrario para la entrada y luego "reproducir" el algoritmo. Siempre que se deba tomar una decisión que dependa de la entrada, se toma el peor camino¹. Una vez que el algoritmo se ha ejecutado hasta su finalización, dividimos la complejidad calculada por el tamaño de la entrada para producir el resultado final.

Nota: Para ser precisos, el peor camino teóricamente posible . Si tiene un vector que duplica dinámicamente su tamaño cada vez que se agota su capacidad, "el peor de los casos" no significa asumir que tendrá que duplicarse en cada inserción porque las inserciones se procesan como una secuencia. Se nos permite (y de hecho debemos) usar estado conocido para eliminar matemáticamente tantos casos "incluso peores" como podamos, incluso cuando la entrada permanece desconocida.

La diferencia mas importante

La diferencia crítica entre el análisis asintótico y amortizado es que el primero depende de la entrada en sí, mientras que el segundo depende de la secuencia de operaciones que ejecutará el algoritmo.

Por lo tanto:

• El análisis asintótico nos permite afirmar que la complejidad del algoritmo cuando se le da una entrada de caso mejor / peor / promedio de tamaño cercano a N está limitada por alguna función F (N), donde N es una variable
• El análisis amortizado nos permite afirmar que la complejidad del algoritmo cuando se le da una entrada de características desconocidas pero el tamaño conocido N no es peor que el valor de una función F (N) - donde N es un valor conocido

La respuesta a esto se define sucintamente en la primera oración del capítulo de Análisis amortizado del libro: Introducción a los algoritmos:

En un análisis amortizado , el tiempo requerido para realizar una secuencia de operaciones de estructura de datos se promedia sobre todas las operaciones realizadas.

Representamos la complejidad del crecimiento de un programa mediante el análisis asintótico, que limita el crecimiento del programa mediante una función y define el peor, el mejor o el caso promedio de ese.

Pero esto puede ser engañoso en los casos en que solo hay un caso en el que la complejidad del programa alcanza un punto máximo, pero en general, el programa no requiere mucho cálculo.

Por lo tanto, tiene más sentido promediar el costo de una secuencia de operaciones, aunque una sola operación pueda resultar costosa. ¡Esto es Análisis Amortizado!

El análisis amortizado es una alternativa a la técnica asintótica utilizada para calcular la complejidad. Nos ayuda a calcular una complejidad más real en términos de practicidad, para poder comparar y decidir entre dos o más algoritmos.

La mejor referencia que he encontrado hasta ahora para comprender el análisis amortizado de algoritmos se encuentra en el libro Introducción a los algoritmos , tercera edición, capítulo 17: "Análisis amortizado". Está todo ahí, explicado mucho mejor que lo que se puede encontrar en una publicación de Stack Overflow. Encontrarás el libro en la biblioteca de cualquier Universidad decente.

El análisis asintótico regular analiza el desempeño de una operación individual de forma asintótica, en función del tamaño del problema. La notación O () es lo que indica un análisis asintótico.

El análisis amortizado (que también es un análisis asintótico) analiza el rendimiento total de múltiples operaciones en una estructura de datos compartida .

La diferencia es que el análisis amortizado típicamente demuestra que el cálculo total requerido para M operaciones tiene una mejor garantía de desempeño que M veces el peor de los casos para la operación individual.

Por ejemplo, una operación individual en un árbol de distribución de tamaño N puede llevar hasta O (N) tiempo. Sin embargo, una secuencia de M operaciones en un árbol de tamaño N está limitada por O (M (1 + log N) + N log N) tiempo, que es aproximadamente O (log N) por operación. Sin embargo, tenga en cuenta que un análisis amortizado es mucho más estricto que un análisis de "caso promedio": demuestra que cualquier secuencia posible de operaciones satisfará su peor caso asintótico.

El análisis amortizado se ocupa del costo total de una serie de ejecuciones de la rutina y de los beneficios que se pueden obtener con ella. Por ejemplo, la búsqueda de una matriz sin clasificar de n elementos para una única coincidencia puede requerir hasta n comparaciones y, por lo tanto, es una (n) complejidad. Sin embargo, si sabemos que se buscarán m elementos en la misma matriz, repetir la tarea total tendría una complejidad O (m * n). Sin embargo, si ordenamos la matriz de antemano, el costo es O (n log (n)), y las búsquedas sucesivas solo toman O (log (n)) para una matriz ordenada. Por lo tanto, el costo total amortizado para m elementos que adoptan este enfoque es O (n * log (n) + m * log (n)). Si m> = n, esto equivale a O (n log (n)) por clasificación previa en comparación con O (n ^ 2) para no clasificar. Por tanto, el coste amortizado es más económico.

En pocas palabras, gastando un poco más desde el principio, podemos ahorrar mucho más tarde.