En informática , la complejidad computacional o simplemente complejidad de un algoritmo es la cantidad de recursos necesarios para ejecutarlo. Se presta especial atención al tiempo de cálculo (generalmente medido por el número de operaciones elementales necesarias) y los requisitos de almacenamiento de memoria . La complejidad de un problema es la complejidad de los mejores algoritmos que permiten resolver el problema.
El estudio de la complejidad de algoritmos dados explícitamente se denomina análisis de algoritmos , mientras que el estudio de la complejidad de los problemas se denomina teoría de la complejidad computacional . Ambas áreas están altamente relacionadas, ya que la complejidad de un algoritmo es siempre un límite superior a la complejidad del problema resuelto por este algoritmo. 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. Además, en la mayoría de los casos, lo único que se sabe acerca de la complejidad de un problema es que es menor que la complejidad de los algoritmos conocidos más eficientes. Por 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 generalmente se expresa como una función n → f ( n ) , donde n es el tamaño de la entrada y f ( n ) es el complejidad en el peor de los casos (el máximo de la cantidad de recursos que se necesitan en todas las entradas de tamaño n ) o la complejidad del caso promedio (el promedio de la cantidad de recursos en todas las entradas de tamaño n ). La complejidad del tiempo 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 de tiempo constante en una computadora determinada y cambian solo en un factor constante cuando se ejecutan en una computadora diferente. La complejidad del espacio generalmente se expresa como la cantidad de memoria requerida por un algoritmo en una entrada de tamaño n .
El recurso más comúnmente considerado es el tiempo. Cuando se utiliza "complejidad" sin reservas, esto generalmente significa complejidad temporal.
Las unidades de tiempo habituales (segundos, minutos, etc.) no se utilizan en la teoría de la complejidad porque dependen demasiado de la elección de una computadora específica y de la evolución de la tecnología. Por ejemplo, una computadora actual puede ejecutar un algoritmo significativamente más rápido que una computadora de la década de 1960; sin embargo, esta no es una característica intrínseca del algoritmo sino más bien una consecuencia de los avances tecnológicos en el hardware informático . La teoría de la complejidad busca cuantificar los requisitos de tiempo intrínsecos de los algoritmos, es decir, las limitaciones de tiempo básicas que un algoritmo impondría a cualquier computadora. Esto se logra contando el número de operaciones elementales que se ejecutan durante el cálculo. Se supone que estas operaciones toman un tiempo constante (es decir, no se ven afectadas por el tamaño de la entrada) en una máquina determinada y, a menudo, se denominan pasos .
Formalmente, la complejidad de los bits se refiere a la cantidad de operaciones en bits que se necesitan para ejecutar un algoritmo. Con la mayoría de los modelos de computación , es igual a la complejidad del tiempo hasta un factor constante. En las computadoras , el número de operaciones en palabras de máquina que se necesitan también es proporcional a la complejidad de los bits. Por tanto, la complejidad del tiempo y la complejidad de los bits son equivalentes para modelos de cálculo realistas.
Otro recurso importante es el tamaño de la memoria de la computadora que se necesita para ejecutar algoritmos.
Para la clase de algoritmos distribuidos que comúnmente son ejecutados por múltiples partes que interactúan, el recurso de mayor interés es la complejidad de la comunicación. Es la cantidad necesaria de comunicación entre las partes ejecutoras.
El número de operaciones aritméticas es otro recurso que se utiliza habitualmente. En este caso se habla de complejidad aritmética . Si se conoce un límite superior para el tamaño de la representación binaria de los números que ocurren durante un cálculo, la complejidad temporal es generalmente el producto de la complejidad aritmética por un factor constante.
Para muchos algoritmos, el tamaño de los números enteros que se utilizan durante un cálculo no está limitado y no es realista considerar que las operaciones aritméticas toman un tiempo constante. Por lo tanto, la complejidad temporal, generalmente denominada complejidad de bits en este contexto, puede ser mucho mayor que la complejidad aritmética. Por ejemplo, la complejidad aritmética del cálculo del determinante de una matriz entera n × n es para los algoritmos habituales ( eliminación gaussiana ). La complejidad de bits de los mismos algoritmos es exponencial en n , porque el tamaño de los coeficientes puede crecer exponencialmente durante el cálculo. Por otro lado, si estos algoritmos se combinan con aritmética multimodular , la complejidad de bits puede reducirse a O ~ ( n 4 ) .
Al ordenar y buscar , el recurso que generalmente se considera es el número de comparaciones de entradas. Generalmente, esta es una buena medida de la complejidad del tiempo si los datos están organizados adecuadamente.
Es imposible contar el número de pasos de un algoritmo en todas las entradas posibles. Como la complejidad generalmente aumenta con el tamaño de la entrada, la complejidad generalmente se expresa como una función del tamaño n (en bits ) de la entrada y, 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 lo tanto, comúnmente se utilizan varias funciones de complejidad.
La complejidad del peor de los casos es el máximo de la complejidad de todas las entradas de tamaño n , y la complejidad del caso promedio es el promedio de la complejidad de todas las entradas de tamaño n (esto tiene sentido, ya que el número de entradas posibles de un determinado el tamaño es finito). Generalmente, cuando se utiliza "complejidad" sin especificar más, esta es la complejidad temporal del peor de los casos que se considera.
Generalmente es difícil calcular con precisión la complejidad del peor de los casos y del caso promedio. Además, estos valores exactos proporcionan poca aplicación práctica, ya que cualquier cambio de computadora o de modelo de cálculo cambiaría un poco la complejidad. Además, el uso de recursos no es crítico para valores pequeños de n , y esto hace que, para n pequeños , la facilidad de implementación sea generalmente más interesante que una baja complejidad.
Por estas razones, generalmente nos centramos en el comportamiento de la complejidad para n grande , 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 números enteros tiene una complejidad que significa que hay una constante tal que la multiplicación de dos números enteros de como máximo n dígitos se puede realizar en un tiempo menor que Este límite es nítido en el sentido de que el peor -la complejidad del caso y la complejidad del caso promedio son, lo que significa que hay una constante tal que estas complejidades son mayores que La base no aparece en estas complejidades, ya que el cambio de base cambia solo las constantes y
La evaluación de la complejidad se basa en la elección de un modelo de cálculo , que consiste en definir las operaciones básicas que se realizan en una unidad de tiempo. Cuando el modelo de cálculo no se especifica explícitamente, generalmente se supone implícitamente que es una máquina de Turing multicinta , ya que varios modelos de cálculo más realistas, como las máquinas de acceso aleatorio, son asintóticamente equivalentes para la mayoría de los problemas. Sólo para problemas muy específicos y difíciles, como la multiplicación de números enteros en el tiempo , se requiere la definición explícita del modelo de cálculo para las pruebas.
Un modelo determinista de computación es un modelo de computación tal que los estados sucesivos de la máquina y las operaciones a realizar están completamente determinados por el estado anterior. Históricamente, los primeros modelos deterministas fueron las funciones recursivas , el cálculo lambda y las máquinas de Turing . El modelo de máquinas de acceso aleatorio (también llamadas máquinas RAM) también se utiliza ampliamente, como una contraparte más cercana a las computadoras reales .
Cuando no se especifica el modelo de cálculo, generalmente se supone que es una máquina de Turing multicinta . Para la mayoría de los algoritmos, la complejidad temporal es la misma en las máquinas de Turing multicinta que en las máquinas RAM, aunque puede ser necesario tener cierto cuidado en cómo se almacenan los datos en la memoria para obtener esta equivalencia.
En un modelo de computación no determinista , como las máquinas de Turing no deterministas , se pueden realizar algunas elecciones en algunos pasos del cálculo. En la teoría de la complejidad, se consideran todas las elecciones posibles simultáneamente, y la complejidad temporal no determinista es el tiempo necesario, cuando siempre se hacen las mejores elecciones. En otras palabras, se considera que el cálculo se realiza simultáneamente en tantos procesadores (idénticos) como sea necesario, y el tiempo de cálculo no determinista es el tiempo empleado por el primer procesador que finaliza el cálculo. Este paralelismo es parcialmente susceptible a la computación cuántica a través de estados entrelazados superpuestos al ejecutar algoritmos cuánticos específicos , como, por ejemplo, la factorización de Shor de números enteros aún pequeños (a marzo de 2018 [actualizar]: 21 = 3 × 7).
Incluso cuando dicho modelo de cálculo aún no es realista, tiene importancia teórica, principalmente relacionada con el problema P = NP , que cuestiona la identidad de las clases de complejidad formadas tomando como mínimo el "tiempo polinómico" y el "tiempo polinómico no determinista". límites superiores. La simulación de un algoritmo NP en una computadora determinista suele llevar un "tiempo exponencial". Un problema es de clase de complejidad NP si puede resolverse en tiempo polinomial en una máquina no determinista. Un problema es NP-completo si, en términos generales, está en NP y no es más fácil que cualquier otro problema NP. Muchos problemas combinatorios , como el problema de la mochila , el problema del viajante y el problema de satisfacibilidad booleana, son NP-completos. Para todos estos problemas, el algoritmo más conocido tiene una complejidad exponencial. Si cualquiera de estos problemas pudiera resolverse en tiempo polinomial en una máquina determinista, entonces todos los problemas NP también podrían resolverse en tiempo polinomial y se tendría P = NP. A partir de 2017, [actualizar]se conjetura generalmente que P ≠ NP, con la implicación práctica de que los peores casos de problemas NP son intrínsecamente difíciles de resolver, es decir, toman más tiempo que cualquier lapso de tiempo razonable (¡décadas!) para obtener longitudes interesantes de entrada.
La computación paralela y distribuida consiste en dividir la computación en varios procesadores, que funcionan simultáneamente. La diferencia entre los distintos modelos radica principalmente en la forma de transmitir la información entre procesadores. Normalmente, en la computación paralela la transmisión de datos entre procesadores es muy rápida, mientras que, en la computación distribuida, la transmisión de datos se realiza a través de una red y, por lo tanto, es mucho más lenta.
El tiempo necesario para un cálculo en N procesadores es al menos el cociente entre N del tiempo necesario para un solo procesador. De hecho, este límite teóricamente óptimo nunca se puede alcanzar, porque algunas subtareas no se pueden paralelizar y es posible que algunos procesadores tengan que esperar un resultado de otro procesador.
Por tanto, el principal problema de complejidad es diseñar algoritmos tales que el producto del tiempo de cálculo por el número de procesadores sea lo más cercano posible al tiempo necesario para el mismo cálculo en un solo procesador.
Una computadora cuántica es una computadora cuyo modelo de computación se basa en la mecánica cuántica . La tesis de Church-Turing se aplica a las computadoras cuánticas; es decir, todo problema que pueda resolverse con una computadora cuántica también puede resolverse con una máquina de Turing. Sin embargo, en teoría, algunos problemas pueden resolverse con una complejidad temporal mucho menor utilizando una computadora cuántica en lugar de una computadora clásica. Esto es, por el momento, puramente teórico, ya que nadie sabe cómo construir una computadora cuántica eficiente.
La teoría de la complejidad cuántica se ha desarrollado para estudiar las clases de complejidad de los problemas resueltos mediante computadoras cuánticas. Se utiliza en criptografía poscuántica , que consiste en diseñar protocolos criptográficos resistentes a ataques de ordenadores cuánticos.
La complejidad de un problema es el mínimo de las complejidades de los algoritmos que pueden resolver el problema [ cita necesaria ] , incluidos los algoritmos desconocidos. Por tanto, la complejidad de un problema no es mayor que la complejidad de cualquier algoritmo que resuelva los problemas.
De ello se deduce que cada complejidad de un algoritmo, que se expresa con notación O grande , es también un límite superior de 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, tales problemas tienen una complejidad que es al menos lineal , es decir, usando notación omega grande , una complejidad
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 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 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. Para este problema, se conoce un algoritmo de complejidad que, por tanto, puede considerarse asintóticamente cuasi óptimo.
Se conoce un límite inferior no lineal para el número de comparaciones necesarias para un algoritmo de clasificación . Por tanto, los mejores algoritmos de clasificación son óptimos, ya que su complejidad es. Este límite inferior resulta del hecho de que hay n ! formas de ordenar n objetos. Como cada comparación se divide en dos partes, este conjunto de n ! órdenes, se debe verificar el número de N de comparaciones que se necesitan para distinguir todos los órdenes, lo que implica la fórmula de Stirling .
Un método estándar para obtener límites inferiores de complejidad consiste en reducir un problema a otro problema. 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 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. Este es el método que se utiliza para demostrar que, si P ≠ NP (una conjetura no resuelta), la complejidad de todo problema NP-completo es para todo entero positivo k .
Evaluar la complejidad de un algoritmo es una parte importante del diseño del algoritmo , 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 será 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 datos de entrada ( big data ). Por ejemplo, cuando uno quiere ordenar alfabéticamente una lista de unos pocos cientos de entradas, como la bibliografía de un libro, cualquier algoritmo debería funcionar bien en menos de un segundo. Por otra parte, 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 comparaciones tendrían que hacer un billón de comparaciones, lo que requeriría alrededor de tres horas a la velocidad de 10 millones de comparaciones por segundo. Por otro lado, la clasificación rápida y la clasificación por combinación solo requieren comparaciones (como complejidad promedio para el primero, como complejidad en el peor de los casos para el segundo). Para n = 1.000.000 , esto da aproximadamente 30.000.000 de comparaciones, lo que sólo tomaría 3 segundos a 10 millones de comparaciones por segundo.
Por tanto, la evaluación de la complejidad puede permitir eliminar muchos algoritmos ineficientes antes de cualquier implementación. Esto también se puede utilizar para ajustar algoritmos complejos sin probar todas las variantes. Al determinar los pasos más costosos de un algoritmo complejo, el estudio de la complejidad permite centrar también en estos pasos el esfuerzo por mejorar la eficiencia de una implementación.
