Complejidad en el peor de los casos

Límite superior de los recursos requeridos por un algoritmo

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.

Definición

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}}}$ ${\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 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 . ${\displaystyle s}$ ${\displaystyle \leq n}$

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

Maneras 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 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 ${\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 peor complejidad posible ". ${\displaystyle {\mathsf {A}}}$ ${\displaystyle O(g(n))}$

o incluso solamente:

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

Ejemplos

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 . ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

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