big - algorithm complexity examples

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.

El análisis amortizado es similar al análisis de casos promedio en el sentido de que se refiere al costo promediado en una secuencia de operaciones. Sin embargo, el análisis de casos promedio se basa en 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 depende de ciertas suposiciones sobre la distribución de probabilidad de las entradas de algoritmo.

Un límite promedio de casos no excluye la posibilidad de que uno tenga "mala suerte" y encuentre una entrada que requiera un tiempo mayor de lo esperado, incluso si las suposiciones para la distribución de probabilidad de las entradas son válidas.

Mis preguntas sobre el fragmento de texto anterior son:

1. En el primer párrafo, ¿cómo el análisis de casos promedio "se basa en suposiciones probabilísticas sobre estructuras de datos y operaciones?" Sé que el análisis de casos promedio depende de la probabilidad de entrada, pero ¿qué significa la declaración anterior?

2. ¿Qué quiere decir 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 la complejidad del tiempo medio del caso, debe hacer suposiciones sobre lo que es el "caso promedio". 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. Tal vez sepa que tiene un tiempo de ejecución de O(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 tenemos mala 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.