¿Cuál es la diferencia entre la complejidad del tiempo promedio y la complejidad del tiempo esperado?

Intuitivamente, la complejidad del tiempo promedio se refiere al comportamiento típico del algoritmo, promediado sobre todas las entradas posibles. La Complejidad de Tiempo Esperada se refiere al comportamiento típico del algoritmo, dada una distribución de entrada contradictoria.

Para ser un poco más formal:
El tiempo de ejecución de un algoritmo depende de dos cosas: (i) la entrada particular que se le da, y (ii) las elecciones aleatorias realizadas durante la ejecución. Existen múltiples “complejidades de tiempo” posibles, dependiendo de si tomamos el promedio o el peor de cada caso.

Si tomamos el peor de los casos en ambos, obtenemos la “Complejidad de tiempo en el peor de los casos”. Esto dice: “No importa qué, el algoritmo terminará después de X pasos”. La “Complejidad de tiempo esperada” toma el peor de los casos y el promedio sobre las decisiones internas. Esto dice: “No importa qué entrada se dé, el algoritmo terminará después de X pasos en promedio”. Finalmente, la “Complejidad de tiempo promedio” toma el promedio sobre las entradas y las decisiones internas. Esto dice: “El algoritmo terminará después de X pasos en promedio, dada una distribución típica de entradas”.

El beneficio de utilizar la complejidad del peor de los casos es obvio: el límite establecido nunca se violará. La desventaja también es obvia: el peor de los casos puede ser muy diferente del caso típico, lo que hace que el límite sea casi sin sentido.

La complejidad del tiempo promedio aborda esta deficiencia, pero potencialmente va demasiado lejos en la otra dirección. Al promediar todas las entradas por igual, se asume firmemente cómo se comportará el usuario. Cualquier declaración sobre la complejidad promedio requiere que asuma una distribución sobre las entradas: use la distribución incorrecta y su límite no tiene valor.

La Complejidad de Tiempo Esperada es la métrica más utilizada y se ubica entre las otras dos. Evita los problemas con la complejidad del tiempo promedio mediante el uso de la entrada del peor de los casos. Evita los problemas de la complejidad del peor de los casos promediando las elecciones internas. En otras palabras, asume un comportamiento “típico” cuando realmente podemos estar seguros de lo que significa “típico”, y utiliza el peor de los casos cuando no podemos.

Obviamente, esto todavía deja algunos detalles que desear. Por ejemplo, la complejidad temporal esperada del Método Simplex es exponencial. Sin embargo, en la práctica, Simplex funciona increíblemente bien. Para abordar esta deficiencia, se utiliza una medida de complejidad aún más matizada, llamada “Complejidad suavizada”. Sin embargo, esto requiere bastante más matemática.