algorithm - ¿Qué es el análisis amortizado de algoritmos?

analysis amortized-analysis (7)

Análisis asintótico

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

Tenga en cuenta que hasta ahora solo hemos hablado sobre el 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 estamos interesados (¿el peor de los casos? ¿el mejor caso? ¿el promedio?).

En la práctica, el término análisis asintótico comúnmente se refiere a la complejidad del tiempo del límite superior de un algoritmo, es decir, el peor rendimiento del caso medido por el tiempo total de ejecución, que se representa mediante la notación Big-Oh (por ejemplo, un algoritmo de clasificación podría ser 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 se dirige al peor de los casos , es decir, el análisis amortizado implica que la métrica es el peor de los casos (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 simples, el análisis amortizado está escogiendo un tamaño arbitrario para la entrada y luego "jugando a través" del algoritmo. Cuando se debe tomar una decisión que depende de la entrada, se toma la peor ruta¹. Una vez que el algoritmo se ha completado, dividimos la complejidad calculada por el tamaño de la entrada para producir el resultado final.

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

La diferencia más importante

La diferencia crítica entre el análisis asintótico y el amortizado es que el primero depende de la entrada misma, 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 mejor / peor / media entrada de caso de tamaño que se aproxima 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

¿Cómo es diferente del análisis asintótico? ¿Cuándo lo usas y por qué?

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

pero todavía no he entendido completamente estos conceptos.

Entonces, ¿alguien puede por favor simplificarlo para mí?

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

Por ejemplo, para una matriz dinámica que duplica su tamaño cuando sea necesario, el análisis asintótico normal solo concluiría que agregarle un artículo cuesta O (n), porque podría necesitar crecer y copiar todos los elementos a la nueva matriz. El análisis amortizado tiene en cuenta que para tener que crecer, se deben haber agregado n / 2 elementos sin causar un crecimiento desde el crecimiento anterior, por lo que agregar un elemento 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 dura sobre lo que hará el rendimiento si realiza tantas acciones.

El análisis amortizado trata el costo total de varias rutinas y los beneficios que se pueden obtener. Por ejemplo, buscar una matriz no ordenada de n elementos para una sola coincidencia puede tomar hasta n comparaciones y, por lo tanto, es o (n) complejidad. Sin embargo, si sabemos que la misma matriz se buscará en m elementos, la repetición de la tarea total tendría 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 toman este enfoque es O (n * log (n) + m * log (n)). Si m> = n, esto equivale a O (n log (n)) por preclasificación en comparación con O (n ^ 2) para no clasificar. Por lo tanto, el costo amortizado es más barato.

En pocas palabras, al gastar un poco más al principio, podemos ahorrar mucho más tarde.

El análisis asintótico regular analiza el rendimiento de una operación individual de forma asintótica, como una 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 generalmente prueba que el cálculo total requerido para las operaciones M tiene una mejor garantía de rendimiento que M veces el peor caso para la operación individual.

Por ejemplo, una operación individual en un árbol desplegable de tamaño N puede tomar hasta O (N) tiempo. Sin embargo, una secuencia de operaciones M 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": prueba que cualquier posible secuencia de operaciones satisfará su peor caso asintótico.

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

Como todos han dicho, el análisis asintótico trata de cómo el rendimiento de una operación dada se adapta a un gran conjunto de datos. El análisis amortizado consiste en 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 el asintótico, y a veces da otros mucho mejores.

Si le preocupa el tiempo total de ejecución de un trabajo más largo, es probable que los mejores límites del análisis amortizado sean los que le interesan. Por eso, los lenguajes de scripting (por ejemplo) a menudo se complacen en crear matrices y tablas hash por algún factor, a pesar de que es una operación costosa. (El crecimiento puede ser una operación O(n) , pero se amortiza O(1) porque lo haces raramente).

Si está haciendo una 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 fallaste en terminarla a tiempo para regresar y ajustar la sierra antes de cortar demasiado ...

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

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

La respuesta a esto se define sucintamente en la primera oración del capítulo de Análisis Amortizado en el 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 promedio del caso.

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

Por lo tanto, tiene más sentido promediar el costo en una secuencia de operaciones, aunque una sola operación sea costosa. ¡Este es un análisis amortizado!

El Análisis Amortizado es una técnica alternativa a la Asintótica utilizada para calcular la complejidad. Nos ayuda a calcular una complejidad más verdadera en términos de practicidad, para comparar y decidir entre dos o más algoritmos.