Diferencia entre el caso promedio y el análisis amortizado

Question

Estoy leyendo un artículo sobre el análisis amortizado de algoritmos. El siguiente es un fragmento de texto.

Análisis de amortización es similar al análisis de los casos del promedio en que es de que se trate con el costo promedio de más de una secuencia de operaciones. Sin embargo, el análisis de casos promedio se basa en las suposiciones probabilísticas sobre las estructuras de datos y las operaciones con el fin de calcular un tiempo de ejecución esperado de un algoritmo. Por lo tanto, su aplicabilidad es dependiendo de ciertas suposiciones sobre la distribución de probabilidad de las entradas de algoritmo .

Un caso consolidado medio no excluye la posibilidad de que uno va a obtener “mala suerte” y encontrar una entrada que requiere más de lo esperado tiempo, incluso si los supuestos de distribución de probabilidad de las entradas son válidas .

Mis preguntas acerca fragmento de texto anterior son:

1. En el primer párrafo, ¿cómo el análisis de los casos promedio “se basan en suposiciones probabilísticas sobre las estructuras y operaciones de datos?” Yo sé análisis de caso promedio depende de la probabilidad de entrada, pero ¿qué significa la declaración anterior?

2. ¿Qué significa el autor en el segundo párrafo que el caso promedio no es válido incluso si la distribución de entrada es válida?

Gracias!

Answer 1

1. para obtener el tiempo promedio de la complejidad de los casos, es necesario hacer suposiciones acerca de lo que el "caso medio" es. Si las entradas son cadenas, ¿cuál es la "cadena promedio"? ¿Solo importa la duración? Si es así, ¿cuál es la longitud promedio de las cadenas que obtendré? Si no, ¿cuál es el/los carácter (es) promedio (s) en estas cadenas? Resulta difícil responder a estas preguntas de manera definitiva si las cadenas son, por ejemplo, apellidos. ¿Cuál es el apellido promedio?

2. En la mayoría de las muestras estadísticas interesantes, el valor máximo es mayor que la media. Esto significa que su análisis de casos promedio a veces subestimará el tiempo/recursos necesarios para ciertos insumos (que son problemáticos). Si lo piensas, para un PDF simétrico, el análisis promedio de casos debe subestimar tanto como sobreestimar. El peor análisis de caso, OTOH, considera solo el (los) caso (s) más problemático (s), por lo que se garantiza que se sobreestimarán.

Answer 2

1. Considere el cálculo del mínimo en una matriz no ordenada. Quizás sepas que tiene O(n) tiempo de ejecución, pero si queremos ser más precisos, la comparación es n/2 en el caso promedio. ¿Por qué esto? porque estamos haciendo una suposición sobre datos; estamos asumiendo que el mínimo puede estar en cada posición con la misma probabilidad. si cambiamos esta suposición, y decimos por ejemplo que la probabilidad de estar en la posición i es, por ejemplo, aumentar con i, podríamos probar un número de comparación diferente, incluso un límite asintótico diferente.

2. En el segundo párrafo, el autor dice que con el análisis de casos promedio podemos tener muy mala suerte y tener un caso promedio medido mayor que el caso térmico; recordando el ejemplo anterior, si no tenemos suerte en m diferentes matrices de tamaño n, y el mínimo es cada vez en la última posición, entonces mediremos un caso promedio de n y no un n/2. Esto no puede suceder solo cuando se prueba un límite amortizado.

Answer 3

El análisis promedio de casos hace suposiciones sobre la entrada que pueden no cumplirse en ciertos casos. Por lo tanto, si su entrada no es aleatoria, en el peor de los casos, el rendimiento real de un algoritmo puede ser mucho más lento que el caso promedio.

El análisis amortizado no hace tales suposiciones, pero considera el rendimiento total de una secuencia de operaciones en lugar de una sola operación.

La inserción de matriz dinámica proporciona un ejemplo simple de análisis amortizado. Un algoritmo es asignar una matriz de tamaño fijo y, a medida que se insertan nuevos elementos, asigne una matriz de tamaño fijo del doble de la anterior cuando sea necesario. En el peor de los casos, una inserción puede requerir tiempo proporcional a la longitud de toda la lista, por lo que en el peor de los casos, la inserción es una operación O (n). Sin embargo, puede garantizar que este caso tan grave no es frecuente, por lo que la inserción es una operación O (1) que utiliza el análisis amortizado. El análisis amortizado se mantiene sin importar cuál sea la entrada.