Complejidad en el peor de los casos

En informática (específicamente en la teoría de la complejidad computacional ), la complejidad del peor caso 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 ). Da un límite superior a los recursos requeridos por el algoritmo.

En el caso del tiempo de ejecución, la complejidad temporal del peor caso indica el tiempo de ejecución más largo realizado por un algoritmo dado 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 caso se utiliza comúnmente para comparar la eficiencia de dos algoritmos.

La complejidad del peor caso de un algoritmo debe contrastarse con su complejidad del caso promedio , que es una medida promedio de la cantidad de recursos que el algoritmo utiliza en una entrada aleatoria.

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

Dado que generalmente nos interesa la dependencia de la complejidad temporal en diferentes longitudes de entrada, abusando de la terminología, la complejidad temporal a veces se refiere a la función , definida 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 . ${\estilo de visualización s}$${\displaystyle \leq n}$

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

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 cierta 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 tales que${\estilo de visualización M}$ ${\estilo de visualización n_{0}}$

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

Con bastante frecuencia, la redacción es:

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

o incluso solamente:

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

Considere la posibilidad de realizar una ordenació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 requiere pasos para realizar la tarea. Sin embargo, la entrada en el peor caso para el algoritmo es cuando los números están ordenados de forma inversa y se requieren pasos para ordenarlos; por lo tanto, la complejidad temporal en el peor caso de la ordenación por inserción es de . ${\estilo de visualización n}$${\displaystyle O(n)}$$Estilo de visualización O(n^{2})}$$Estilo de visualización O(n^{2})}$

• Análisis de algoritmos

• 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ágs. 25-27.
• Oded Goldreich. Complejidad computacional: una perspectiva conceptual. Cambridge University Press, 2008. ISBN 0-521-88473-X , p.32.