El análisis del caso peor y el caso promedio son medidas bien conocidas para la complejidad de un algoritmo. El análisis suavizado recientemente ha surgido como otro paradigma para explicar por qué algunos algoritmos que son exponenciales en el peor de los casos funcionan tan bien en la práctica, por ejemplo, el algoritmo simplex.
Mi pregunta es: ¿hay otros paradigmas para medir la complejidad de un algoritmo? Estoy particularmente interesado en los que intentan explicar por qué algunos algoritmos que tienen una mala complejidad en el peor de los casos funcionan bien en la práctica.