En informática, la complejidad del peor de los casos (generalmente indicada en notación asintótica) mide los recursos (por ejemplo, tiempo de ejecución, memoria) que requiere un algoritmo dada una entrada de tamaño arbitrario (comúnmente indicada como n o N ). Da un límite superior a los recursos requeridos por el algoritmo.
En el caso del tiempo de ejecución, la complejidad de tiempo del peor de los casos indica el tiempo de ejecución más largo realizado por un algoritmo dada cualquier entrada de tamaño n y, por lo tanto, garantiza que el algoritmo terminará en el período de tiempo indicado. El orden de crecimiento (por ejemplo, lineal, logarítmico) de la complejidad del caso más desfavorable se usa comúnmente para comparar la eficiencia de dos algoritmos.
La complejidad del caso más desfavorable de un algoritmo debe contrastarse con su complejidad del caso promedio , que es una medida promedio de la cantidad de recursos que utiliza el algoritmo en una entrada aleatoria.
Dado un modelo de computación y un algoritmo A que se detiene en cada entrada x , la aplicación t A :{0, 1}*→ N se denomina complejidad temporal de A si, para cada x , A se detiene exactamente después de t A ( x ) pasos.
Dado que generalmente estamos interesados en la dependencia de la complejidad del tiempo en diferentes longitudes de entrada, abusando de la terminología, la complejidad del tiempo a veces se refiere al mapeo T A : N → N , definido por T A ( n ):= max x ∈{0 , 1} norte {t A ( x )}.
Considere realizar una ordenación por inserción en n números en una máquina de acceso aleatorio . El mejor caso para el algoritmo es cuando los números ya están ordenados, lo que requiere O( n ) pasos para realizar la tarea. Sin embargo, la entrada en el peor de los casos para el algoritmo es cuando los números se ordenan de forma inversa y se necesitan O( n 2 ) pasos para ordenarlos; por lo tanto, la complejidad temporal del tipo de inserción en el peor de los casos es de O( n 2 ).