Análisis probabilístico de algoritmos

En el análisis de algoritmos , el análisis probabilístico es un método para estimar la complejidad computacional de un algoritmo o problema computacional. Parte de una suposición sobre una distribución de probabilidad en el conjunto de todas las entradas posibles. Esta suposición se utiliza para diseñar un algoritmo eficiente o para derivar la complejidad de un algoritmo conocido. Este método no es idéntico al de los algoritmos probabilísticos , pero ambos pueden combinarse.

Para algoritmos no probabilísticos, más específicamente deterministas , los tipos más comunes de estimaciones de complejidad probabilística son la complejidad en el caso promedio y la complejidad casi siempre. Para obtener la complejidad en el caso promedio, dada una distribución de entrada, se evalúa el tiempo esperado de un algoritmo, mientras que para la estimación de complejidad casi siempre, se evalúa si el algoritmo admite una estimación de complejidad dada que se cumple casi con seguridad .

En el análisis probabilístico de algoritmos probabilísticos (aleatorizados), además de las distribuciones de entrada, también se tienen en cuenta las distribuciones o el promedio de todas las opciones posibles en los pasos aleatorios.

• Análisis amortizado
• Complejidad del caso promedio
• Mejor caso, peor caso y caso promedio
• Autorreducción aleatoria
• Principio de decisión diferida

• Frieze, Alan M.; Reed, Bruce (1998), "Análisis probabilístico de algoritmos", en Habib, Michel; McDiarmid, Colin; Ramirez-Alfonsin, Jorge; Reed, Bruce (eds.), Métodos probabilísticos para matemáticas discretas algorítmicas , Algorithms and Combinatorics, vol.  16, Springer, pp. 36–92 , doi : 10.1007/978-3-662-12788-9_2 , ISBN  9783662127889
• Hofri, Micha (1987), Análisis probabilístico de algoritmos: sobre metodologías computacionales para la evaluación del rendimiento de algoritmos informáticos , Springer, doi : 10.1007/978-1-4612-4800-2 , ISBN 9781461248002
• Frieze, AM (1990), "Análisis probabilístico de algoritmos de grafos", en Tinhofer, G.; Mayr, E.; Noltemeier, H.; Syslo, MM (eds.), Teoría computacional de grafos , Computing Supplementa, vol.  7, Springer, pp. 209–233 , doi : 10.1007/978-3-7091-9076-0_11 , ISBN  9783709190760