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 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 muy relacionadas, ya que la complejidad de un algoritmo es siempre un límite superior de la complejidad del problema resuelto por este algoritmo. Además, para diseñar algoritmos eficientes, a menudo es 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 sobre la complejidad de un problema es que es menor que la complejidad de los algoritmos conocidos más eficientes. 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 (la máxima de la cantidad de recursos que se necesitan sobre todas las entradas de tamaño n ) o la complejidad del caso promedio (el promedio de la cantidad de recursos sobre todas las entradas de tamaño n ). La complejidad de 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 constante de tiempo en una computadora dada y cambian solo por un factor constante cuando se ejecutan en una computadora diferente. La complejidad de espacio generalmente se expresa como la cantidad de memoria requerida por un algoritmo en una entrada de tamaño n .
El recurso que se considera con más frecuencia es el tiempo. Cuando se utiliza el término "complejidad" sin calificativo, generalmente se refiere a la 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 un ordenador específico y de la evolución de la tecnología. Por ejemplo, un ordenador actual puede ejecutar un algoritmo significativamente más rápido que un ordenador de la década de 1960; sin embargo, esto no es una característica intrínseca del algoritmo sino más bien una consecuencia de los avances tecnológicos en el hardware de los ordenadores . La teoría de la complejidad busca cuantificar los requisitos de tiempo intrínsecos de los algoritmos, es decir, las restricciones de tiempo básicas que un algoritmo impondría a cualquier ordenador. 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 bits se refiere a la cantidad de operaciones en bits que se necesitan para ejecutar un algoritmo. En la mayoría de los modelos de computación , es igual a la complejidad temporal hasta un factor constante. En las computadoras , la cantidad de operaciones en palabras de máquina que se necesitan también es proporcional a la complejidad de bits. Por lo tanto, la complejidad temporal y la complejidad de bits son equivalentes para los modelos realistas de computación.
Otro recurso importante es el tamaño de la memoria de la computadora que se necesita para ejecutar algoritmos.
En el caso de los algoritmos distribuidos que suelen ejecutar varias partes que interactúan entre sí, el recurso que más interesa es la complejidad de la comunicación, es decir, la cantidad de comunicación necesaria entre las partes que los ejecutan.
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 se producen 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á acotado, y no es realista considerar que las operaciones aritméticas toman un tiempo constante. Por lo tanto, la complejidad temporal, generalmente llamada 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 ) .
En la ordenación y búsqueda , el recurso que generalmente se considera es el número de comparaciones de entradas. Esto suele ser una buena medida de la complejidad temporal 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 se expresa típicamente 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, se utilizan comúnmente varias funciones de complejidad.
La complejidad del peor caso es el máximo de la complejidad sobre todas las entradas de tamaño n , y la complejidad del caso promedio es el promedio de la complejidad sobre todas las entradas de tamaño n (esto tiene sentido, ya que la cantidad de entradas posibles de un tamaño determinado es finita). Generalmente, cuando se utiliza "complejidad" sin especificar más, esta es la complejidad temporal del peor caso que se considera.
En general, es difícil calcular con precisión la complejidad del peor de los casos y la del caso promedio. Además, estos valores exactos ofrecen 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 complejidad baja.
Por estas razones, generalmente se presta atención al comportamiento de la complejidad para valores grandes de n , es decir, a su comportamiento asintótico cuando n tiende al infinito. Por lo tanto, la complejidad se expresa generalmente mediante la notación O grande .
Por ejemplo, el algoritmo habitual para la multiplicación de números enteros tiene una complejidad de esto 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 preciso en el sentido de que la complejidad del peor caso y la complejidad del caso promedio son lo que significa que hay una constante tal que estas complejidades son mayores que El radix no aparece en estas complejidades, ya que al cambiar el radix solo se cambian 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 se trata de una máquina de Turing de múltiples cintas , 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. Solo 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 demostraciones.
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 precedente. 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 se trata de 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 no determinista de computación , como las máquinas de Turing no deterministas , algunas elecciones pueden realizarse 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 realizan 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 termina el cálculo. Este paralelismo es parcialmente susceptible a la computación cuántica a través de estados entrelazados superpuestos en la ejecución de 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).
Aunque un modelo computacional de este tipo no es aún realista, tiene importancia teórica, relacionada principalmente con el problema P = NP , que cuestiona la identidad de las clases de complejidad formadas al tomar el "tiempo polinomial" y el "tiempo polinomial no determinista" como límites superiores mínimos. Simular un algoritmo NP en una computadora determinista generalmente requiere "tiempo exponencial". Un problema está en la clase de complejidad NP si se puede resolver 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 complejidad exponencial. Si cualquiera de estos problemas pudiera resolverse en tiempo polinómico en una máquina determinista, entonces todos los problemas NP también podrían resolverse en tiempo polinómico, 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 longitudes de entrada interesantes.
La computación paralela y distribuida consiste en dividir la computación en varios procesadores que trabajan 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 tanto, es mucho más lenta.
El tiempo necesario para un cálculo en N procesadores es al menos el cociente por 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 algunos procesadores pueden tener que esperar un resultado de otro procesador.
El principal problema de complejidad es, por tanto, 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.
Un ordenador cuántico es un ordenador cuyo modelo de cálculo se basa en la mecánica cuántica . La tesis de Church-Turing se aplica a los ordenadores cuánticos, es decir, todo problema que pueda resolverse con un ordenador cuántico también puede resolverse con una máquina de Turing. Sin embargo, algunos problemas pueden resolverse teóricamente con una complejidad temporal mucho menor utilizando un ordenador cuántico en lugar de un ordenador clásico. Esto es, por el momento, puramente teórico, ya que nadie sabe cómo construir un ordenador cuántico eficiente.
La teoría de la complejidad cuántica se ha desarrollado para estudiar las clases de complejidad de los problemas que se resuelven mediante ordenadores cuánticos. Se utiliza en la criptografía postcuántica , que consiste en diseñar protocolos criptográficos resistentes a los ataques de los ordenadores cuánticos.
La complejidad de un problema es el ínfimo de las complejidades de los algoritmos que pueden resolver el problema [ cita requerida ] , incluidos los algoritmos desconocidos. Por lo 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 la notación O mayúscula , es también un límite superior de la complejidad del problema correspondiente.
Por otra parte, generalmente es difícil obtener límites inferiores no triviales para la complejidad del problema, y hay 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
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 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 puede considerarse asintóticamente cuasi-óptimo.
Se conoce un límite inferior no lineal de para el número de comparaciones necesarias para un algoritmo de ordenamiento . Por lo tanto, los mejores algoritmos de ordenamiento 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 divide en dos partes este conjunto de n ! órdenes, el número de N de comparaciones que se necesitan para distinguir todos los órdenes debe verificar lo que implica por 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 sin resolver), la complejidad de cada problema NP-completo es para cada 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 perderá importancia como resultado de la ley de Moore , que postula el crecimiento exponencial de la potencia de las computadoras modernas . Esto es erróneo 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 otro lado, para una lista de un millón de entradas (los números de teléfono de una ciudad grande, por ejemplo), los algoritmos elementales que requieren comparaciones tendrían que hacer un billón de comparaciones, lo que necesitaría alrededor de tres horas a la velocidad de 10 millones de comparaciones por segundo. Por otro lado, el quicksort y el merge sort solo requieren comparaciones (como complejidad de caso promedio para el primero, como complejidad de caso peor 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 esta manera, la evaluación de la complejidad puede permitir eliminar muchos algoritmos ineficientes antes de cualquier implementación. Esto también puede utilizarse 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 también permite centrar en estos pasos el esfuerzo para mejorar la eficiencia de una implementación.
