En la teoría de la complejidad computacional , la complejidad de caso promedio de un algoritmo es la cantidad de algún recurso computacional (generalmente tiempo) utilizado por el algoritmo, promediado sobre todas las entradas posibles. Con frecuencia se contrasta con la complejidad del peor de los casos, que considera la complejidad máxima del algoritmo sobre todas las entradas posibles.
Hay tres motivaciones principales para estudiar la complejidad del caso promedio. [1] Primero, aunque algunos problemas pueden ser intratables en el peor de los casos, las entradas que provocan este comportamiento rara vez ocurren en la práctica, por lo que la complejidad del caso promedio puede ser una medida más precisa del rendimiento de un algoritmo. En segundo lugar, el análisis de complejidad de casos promedio proporciona herramientas y técnicas para generar instancias difíciles de problemas que se pueden utilizar en áreas como la criptografía y la desaleatorización . En tercer lugar, la complejidad del caso promedio permite discriminar el algoritmo más eficiente en la práctica entre algoritmos de complejidad equivalente del mejor caso (por ejemplo, Quicksort ).
El análisis de casos promedio requiere una noción de una entrada "promedio" para un algoritmo, lo que lleva al problema de diseñar una distribución de probabilidad sobre las entradas. Alternativamente, se puede utilizar un algoritmo aleatorio . El análisis de tales algoritmos conduce a la noción relacionada de una complejidad esperada . [2] : 28
El rendimiento de caso promedio de los algoritmos se ha estudiado desde que se desarrollaron las nociones modernas de eficiencia computacional en la década de 1950. Gran parte de este trabajo inicial se centró en problemas para los que ya se conocían algoritmos de tiempo polinómico del peor de los casos. [3] En 1973, Donald Knuth [4] publicó el Volumen 3 de El arte de la programación informática , que analiza de forma exhaustiva el rendimiento de los casos promedio de los algoritmos para problemas que se pueden resolver en el tiempo polinomial del peor de los casos, como la clasificación y la búsqueda de la mediana.
Un algoritmo eficiente para problemas NP-completos generalmente se caracteriza por ejecutarse en tiempo polinomial para todas las entradas; esto es equivalente a requerir una complejidad eficiente en el peor de los casos. Sin embargo, un algoritmo que es ineficaz en un número "pequeño" de entradas puede seguir siendo eficaz para "la mayoría" de las entradas que se producen en la práctica. Por lo tanto, es deseable estudiar las propiedades de estos algoritmos donde la complejidad del caso promedio puede diferir de la complejidad del caso más desfavorable y encontrar métodos para relacionar los dos.
Las nociones fundamentales de la complejidad del caso promedio fueron desarrolladas por Leonid Levin en 1986 cuando publicó un artículo de una página [5] que definía la complejidad y la completitud del caso promedio al tiempo que brindaba un ejemplo de un problema completo para distNP, el análogo del caso promedio de NP .