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 a los requisitos de tiempo y 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 llama análisis de algoritmos , mientras que el estudio de la complejidad de problemas se llama 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 en 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 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 del peor caso (el máximo 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 del tiempo generalmente se expresa como el número de operaciones elementales requeridas en una entrada de tamañon , donde se supone que las operaciones elementales toman una cantidad de tiempo constante en una computadora dada y cambian solo por 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 usa "complejidad" sin calificación, generalmente significa complejidad de tiempo.
Las unidades habituales de tiempo (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 de hoy 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 de las computadoras . 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 colocaría en cualquier computadora. Esto se logra contando el número de operaciones elementalesque 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 .
El número de operaciones aritméticas es otro recurso que se utiliza comúnmente. En este caso, se habla de complejidad aritmética . Si se conoce un límite superior en el tamaño de la representación binaria de los números que ocurren durante un cálculo, la complejidad del tiempo es generalmente el producto de la complejidad aritmética por un factor constante.