En el análisis de algoritmos , el análisis probabilístico de algoritmos es un enfoque para estimar la complejidad computacional de un algoritmo o un problema computacional. Se parte de un supuesto sobre una distribución probabilística del conjunto de todas las entradas posibles. Esta suposición se utiliza luego para diseñar un algoritmo eficiente o para derivar la complejidad de un algoritmo conocido. Este enfoque no es el mismo que el de los algoritmos probabilísticos , pero los dos pueden combinarse.
Para los algoritmos no probabilísticos, más específicamente deterministas , los tipos más comunes de estimaciones de complejidad son la complejidad del caso promedio y la complejidad casi siempre. Para obtener la complejidad del 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 que el algoritmo admite una estimación de complejidad dada que casi con seguridad se cumple.
En el análisis probabilístico de algoritmos probabilísticos (aleatorios), también se tienen en cuenta las distribuciones o el promedio de todas las opciones posibles en pasos aleatorios, además de las distribuciones de entrada.