Complejidad en el peor de los casos

Límite superior de los recursos requeridos por un algoritmo

En informática (específicamente teoría de la complejidad computacional ), la complejidad del peor de los casos mide los recursos (por ejemplo, tiempo de ejecución, memoria ) que requiere un algoritmo dada una entrada de tamaño arbitrario (comúnmente denotada como n en notación asintótica ). Proporciona un límite superior a los recursos requeridos por el algoritmo.

En el caso del tiempo de ejecución, la complejidad del tiempo en el 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 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 utiliza comúnmente para comparar la eficiencia de dos algoritmos.

La complejidad del peor de los casos 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.

Definición

Dado un modelo de cálculo y un algoritmo que se detiene en cada entrada , el mapeo se denomina complejidad temporal de si, para cada cadena de entrada , se detiene exactamente después de los pasos. ${\displaystyle {\mathsf {A}}}$ ${\displaystyle s}$ ${\displaystyle t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N} }$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle s}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle t_{\mathsf {A}}(s)}$

Dado que normalmente estamos interesados ​​en la dependencia de la complejidad del tiempo de diferentes longitudes de entrada, abusando de la terminología, la complejidad del tiempo a veces se refiere al mapeo , definido por la complejidad máxima. ${\displaystyle t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)}$

de entradas con longitud o tamaño . ${\displaystyle s}$ ${\displaystyle \leq n}$

Se pueden dar definiciones similares para complejidad espacial , complejidad de aleatoriedad, etc.

formas de hablar

Muy frecuentemente, la complejidad de un algoritmo se da en notación asintótica Big-O , que da su tasa de crecimiento en la forma con una determinada función de comparación de valor real y el significado: ${\displaystyle t_{\mathsf {A}}}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle t_{\mathsf {A}}=O(g(n))}$ ${\displaystyle g(n)}$

• Existe un número real positivo y un número natural tal que ${\displaystyle M}$ ${\displaystyle n_{0}}$

${\displaystyle |t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{ for all }}n\geq n_{0}.}$

Con bastante frecuencia, la redacción es:

• "El algoritmo tiene la complejidad del peor de los casos ". ${\displaystyle {\mathsf {A}}}$ ${\displaystyle O(g(n))}$

o incluso solo:

• "El algoritmo tiene complejidad ". ${\displaystyle {\mathsf {A}}}$ ${\displaystyle O(g(n))}$

Ejemplos

Considere realizar una clasificación por inserción de 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 toma medidas 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 toman medidas para ordenarlos; por lo tanto, la complejidad temporal del tipo de inserción en el peor de los casos es de . ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

Ver también

• Análisis de algoritmos.

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. Cambridge University Press, 2008. ISBN 0-521-88473-X , p.32.