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 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 se expresa típicamente 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 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 .
Formalmente, la complejidad de bits se refiere al número de operaciones en bits que se necesitan para ejecutar un algoritmo. Con la mayoría de los modelos de computación , iguala la complejidad del tiempo 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. Entonces, la complejidad de tiempo y la complejidad de bits son equivalentes para modelos realistas de computación.