Complejidad computacional

En informática , la complejidad computacional , o simplemente complejidad, de un algoritmo es la cantidad de recursos necesarios para ejecutarlo. ^{[ 1 ]} Se presta especial atención al tiempo de cálculo (generalmente medido por el número de operaciones elementales necesarias) y a los requisitos de memoria . La complejidad de un problema es la complejidad de los mejores algoritmos que permiten resolverlo.

El estudio de la complejidad de algoritmos explícitamente dados se denomina análisis de algoritmos , mientras que el estudio de la complejidad de problemas se denomina teoría de la complejidad computacional . Ambas áreas están estrechamente relacionadas, ya que la complejidad de un algoritmo siempre representa una cota superior de la complejidad del problema que resuelve. Además, para diseñar algoritmos eficientes, suele ser fundamental comparar la complejidad de un algoritmo específico con la complejidad del problema a resolver. Asimismo, en la mayoría de los casos, lo único que se sabe sobre la complejidad de un problema es que no supera la complejidad de los algoritmos más eficientes conocidos. Por lo tanto, existe una gran superposición entre el análisis de algoritmos y la teoría de la complejidad.

Como la cantidad de recursos necesarios para ejecutar un algoritmo generalmente varía con el tamaño de la entrada, la complejidad se expresa típicamente como una función n ↦ f ( n ) , donde n es el tamaño de la entrada y f ( n ) es la complejidad del peor caso (el máximo de la cantidad de recursos que se necesitan para todas las entradas de tamaño n ) o la complejidad del caso promedio (el promedio de la cantidad de recursos para todas las entradas de tamaño n ). La complejidad temporal generalmente se expresa como el número de operaciones elementales requeridas en una entrada de tamaño n , donde se supone que las operaciones elementales toman una cantidad constante de tiempo en una computadora dada y cambian solo por un factor constante cuando se ejecutan en una computadora diferente. La complejidad espacial generalmente se expresa como la cantidad de memoria requerida por un algoritmo en una entrada de tamaño n .

Es imposible contar el número de pasos de un algoritmo para todas las entradas posibles. Dado que la complejidad generalmente aumenta con el tamaño de la entrada, se suele expresar como una función del tamaño n (en bits ) de la entrada; por lo tanto, la complejidad es una función de n . Sin embargo, la complejidad de un algoritmo puede variar drásticamente para diferentes entradas del mismo tamaño. Por consiguiente, se suelen utilizar diversas funciones de complejidad.

La complejidad en el peor de los casos es el máximo de la complejidad para todas las entradas de tamaño n , y la complejidad en el caso promedio es el promedio de la complejidad para todas las entradas de tamaño n (esto tiene sentido, ya que el número de posibles entradas de un tamaño dado es finito). Generalmente, cuando se usa el término "complejidad" sin especificarlo, se considera la complejidad temporal en el peor de los casos.

Generalmente, resulta difícil calcular con precisión la complejidad en el peor de los casos y en el caso promedio. Además, estos valores exactos tienen poca utilidad práctica, ya que cualquier cambio de ordenador o de modelo de cálculo modificaría la complejidad. Asimismo, el uso de recursos no es crítico para valores pequeños de n , lo que implica que, para valores pequeños de n , la facilidad de implementación suele ser más importante que una baja complejidad.

Por estas razones, generalmente uno se centra en el comportamiento de la complejidad para valores grandes de n , es decir, en su comportamiento asintótico cuando n tiende al infinito. Por lo tanto, la complejidad generalmente se expresa utilizando la notación O grande .

Por ejemplo, el algoritmo habitual para la multiplicación de enteros tiene una complejidad de${\displaystyle O(n^{2});}$Esto significa que hay una constante${\displaystyle c_{u}}$de tal manera que la multiplicación de dos enteros de como máximo n dígitos se pueda realizar en un tiempo menor que${\displaystyle c_{u}n^{2}.}$Este límite es preciso en el sentido de que la complejidad del peor caso y la complejidad del caso promedio son${\displaystyle \Omega (n^{2}),}$lo que significa que también hay una constante${\displaystyle c_{l}}$de tal manera que estas complejidades son mayores que${\displaystyle c_{l}n^{2}.}$La base no aparece en estas complejidades, ya que al cambiar la base solo cambian las constantes.${\displaystyle c_{u}}$y${\displaystyle c_{l}.}$

La evaluación de la complejidad se basa en la elección de un modelo de computación , que consiste en definir las operaciones básicas que se realizan en una unidad de tiempo. Cuando el modelo de computación no se especifica explícitamente, generalmente se asume implícitamente que es una máquina de Turing de cintas múltiples , ya que varios modelos de computación más realistas, como las máquinas de acceso aleatorio, son asintóticamente equivalentes para la mayoría de los problemas. Solo para problemas muy específicos y difíciles, como la multiplicación de enteros en tiempo${\displaystyle O(n\log n),}$que la definición explícita del modelo de computación es necesaria para las demostraciones.

De manera informal, la complejidad de un problema se define como la complejidad mínima de todos los algoritmos, incluidos los desconocidos, que lo resuelven, aunque dicha complejidad mínima podría no existir. Por lo tanto, la complejidad de un problema no es mayor que la complejidad de ningún algoritmo que lo resuelva.

De ello se deduce que cualquier complejidad de un algoritmo que se exprese con la notación O grande , es también una cota superior para la complejidad del problema correspondiente.

Por otro lado, generalmente es difícil obtener límites inferiores no triviales para la complejidad del problema, y ​​existen pocos métodos para obtener dichos límites inferiores.

Para resolver la mayoría de los problemas, es necesario leer todos los datos de entrada, lo que, normalmente, requiere un tiempo proporcional al tamaño de los datos. Por lo tanto, dichos problemas tienen una complejidad que es al menos lineal , es decir, utilizando la notación omega grande , una complejidad${\displaystyle \Omega (n).}$

La solución de algunos problemas, típicamente en álgebra computacional y geometría algebraica computacional , puede ser muy grande. En tal caso, la complejidad está limitada inferiormente por el tamaño máximo de la salida, ya que la salida debe escribirse. Por ejemplo, un sistema de n ecuaciones polinómicas de grado d en n indeterminadas puede tener hasta${\displaystyle d^{n}}$soluciones complejas , si el número de soluciones es finito (este es el teorema de Bézout ). Como estas soluciones deben escribirse, la complejidad de este problema es${\displaystyle \Omega (d^{n}).}$Para este problema, un algoritmo de complejidad${\displaystyle d^{O(n)}}$es conocido, lo que puede considerarse como asintóticamente óptimo.

Un límite inferior no lineal de${\displaystyle \Omega (n\log n)}$es conocido por el número de comparaciones necesarias para un algoritmo de ordenación . Por lo tanto, los mejores algoritmos de ordenación son asintóticamente óptimos, ya que su complejidad es${\displaystyle O(n\log n).}$Este límite inferior resulta del hecho de que hay n ! maneras de ordenar n objetos. Como cada comparación divide en dos partes este conjunto de n ! órdenes, el número de comparaciones N que se necesitan para distinguir todos los órdenes debe validarse${\displaystyle 2^{N}>n!,}$lo cual implica${\displaystyle N=\Omega (n\log n),}$por la fórmula de Stirling .

Un método estándar para demostrar cotas inferiores para la complejidad de los problemas consiste en reducir un problema a otro. Más precisamente, supongamos que se puede codificar un problema A de tamaño n en un subproblema de tamaño f ( n ) de un problema B , y que la complejidad de A es${\displaystyle \Omega (g(n)).}$Sin pérdida de generalidad, se puede suponer que la función f aumenta con n y tiene una función inversa h . Entonces, la complejidad del problema B es${\displaystyle \Omega (g(h(n))).}$Este es el método que se utiliza para demostrar que, si P ≠ NP (una conjetura sin resolver), la complejidad de cada problema NP-completo es${\displaystyle \Omega (n^{k}),}$para cada entero positivo k .

Evaluar la complejidad de un algoritmo es una parte importante del diseño de algoritmos , ya que proporciona información útil sobre el rendimiento que se puede esperar.

Es un error común pensar que la evaluación de la complejidad de los algoritmos se volverá menos importante como resultado de la ley de Moore , que postula el crecimiento exponencial de la potencia de las computadoras modernas . Esto es incorrecto porque este aumento de potencia permite trabajar con grandes cantidades de datos de entrada ( big data ). Por ejemplo, cuando se quiere ordenar alfabéticamente una lista de unos cientos de entradas, como la bibliografía de un libro, cualquier algoritmo debería funcionar bien en menos de un segundo. Por otro lado, para una lista de un millón de entradas (los números de teléfono de una gran ciudad, por ejemplo), los algoritmos elementales que requieren${\displaystyle O(n^{2})}$Las comparaciones tendrían que hacer un billón de comparaciones, lo que necesitaría alrededor de tres horas a una velocidad de 10 millones de comparaciones por segundo. Por otro lado, el ordenamiento rápido y el ordenamiento por fusión solo requieren${\displaystyle n\log _{2}n}$comparaciones (como complejidad en el caso promedio para el primero, como complejidad en el peor caso para el segundo). Para n = 1.000.000 , esto da aproximadamente 30.000.000 de comparaciones, lo que solo tomaría 3 segundos a 10 millones de comparaciones por segundo.

De este modo, la evaluación de la complejidad permite descartar muchos algoritmos ineficientes antes de su implementación. Esto también puede utilizarse para optimizar algoritmos complejos sin necesidad de probar todas las variantes. Al determinar los pasos más costosos de un algoritmo complejo, el estudio de la complejidad permite centrar los esfuerzos para mejorar la eficiencia de la implementación en dichos pasos.

• Complejidad computacional de las operaciones matemáticas
• Lista de complejidad del problema del cartero chino
• Teorema maestro (análisis de algoritmos)

• Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno , Cambridge , ISBN 978-0-521-42426-4, Zbl 1193.68112 
• Calude, Cristian (1988), Teorías de la complejidad computacional , Elsevier , pág.  487, ISBN 9780444703569
• Du, Ding-Zhu; Ko, Ker-I (2000), Teoría de la complejidad computacional , John Wiley & Sons , ISBN 978-0-471-34506-0ISSN 0167-5060​ 
• Garey, Michael R.; Johnson , David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , Serie de libros en ciencias matemáticas (1.ª  ed.), Nueva York: WH Freeman and Company , ISBN 9780716710455, MR 0519066 , OCLC 247570676  
• Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press
• van Leeuwen, Jan , ed. (1990), Manual de informática teórica (vol. A): algoritmos y complejidad , MIT Press , ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Complejidad computacional (1.ª  ed.), Addison Wesley, ISBN 0-201-53082-1
• Sipser, Michael (2006), Introducción a la teoría de la computación (2.ª  ed.), EE. UU.: Thomson Course Technology , ISBN 0-534-95097-3