Análisis probabilístico de algoritmos
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. Comienza con una suposición 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 ambos pueden combinarse.
En el caso de algoritmos no probabilísticos, más específicamente deterministas , los tipos más comunes de estimaciones de complejidad son la complejidad de caso promedio y la complejidad de casi siempre. Para obtener la complejidad de 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 de casi siempre, se evalúa que 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 (aleatorios), además de las distribuciones de entrada, también se tienen en cuenta las distribuciones o el promedio de todas las opciones posibles en pasos aleatorios.
Véase también
- Análisis amortizado
- Complejidad de caso promedio
- Mejor, peor y promedio de los casos
- Autorreducibilidad aleatoria
- Principio de decisión diferida
Referencias
- 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, págs. 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 desempeño 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.), Computational Graph Theory , Computing Supplementa, vol. 7, Springer, págs. 209–233, doi :10.1007/978-3-7091-9076-0_11, ISBN 9783709190760
 | Este artículo relacionado con algoritmos o estructuras de datos es un esbozo . Puedes ayudar a Wikipedia expandiéndolo. |
