En informática, la complejidad del peor de los casos (generalmente denotada 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 denotado 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 caso 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 finalizará en el período de tiempo indicado. El orden de crecimiento (por ejemplo, lineal, logarítmico) de la complejidad del peor de los casos se usa comúnmente para comparar la eficiencia de dos algoritmos.
La complejidad del peor de los casos de un algoritmo debe contrastarse con su complejidad de caso promedio , que es una medida promedio de la cantidad de recursos que usa el algoritmo en una entrada aleatoria.
Definición
Dado un modelo de cálculo y un algoritmo A que se detiene en cada entrada x , el mapeo t A : {0, 1} * → N se denomina complejidad de tiempo 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} n {t A ( x )}.
Se pueden dar definiciones similares para la complejidad del espacio, la complejidad de la aleatoriedad, etc.
Ejemplos de
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 al revés y se necesitan O ( n 2 ) pasos para ordenarlos; por lo tanto, el peor caso de complejidad temporal del tipo de inserción es O ( n 2 ).
Ver también
Referencias
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capítulo 2.2: Análisis de algoritmos, páginas 25-27.
- Oded Goldreich. Complejidad computacional: una perspectiva conceptual. Prensa de la Universidad de Cambridge, 2008. ISBN 0-521-88473-X , página 32.