complejidad

La complejidad en los algoritmos computacionales, no hace otra cosa que estudiar, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos que son comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). De misma manera se pueden estudiar otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo.
Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfacibilidad booleana y el problema del viajante, un camino Hamiltoniano para recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen la propiedad de que su solución puede ser verificada efectivamente.
Esta complejidad se mide por medio de una función f(n) que da el tiempo y espacio de almacenamiento necesario para la ejecución del mismo. La n representa el tamaño de los datos de entrada. Dicho de otra manera, en lugar de calcular el tiempo exacto que tardará el algoritmo, se calcula la cantidad de operaciones en función del tamaño de la entrada (n).