Complejidad Computacional

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que esta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable.

Tasa de crecimiento:

La tasa de crecimiento de una función mide el rendimiento asintótico de la función, conforme la entrada va creciendo intuitivamente la tasa de crecimiento se determina por el elemento más significativo de la misma.

O(1)=Constante

O(log(n))=Logaritmico

O(n)=Lineal

O(n log(n))=n log n

O(n^2)=Cuadratica

O(n^3)=Cúbica

O(n^r)=Polinomial r>=0

O(b^n)=Exponencial b>1

O(n!)=Factorial


Crecimiento de las funciones más comunes:
n log2(n) n2 n3 2n n!
5 2 25 125 32 120
10 3 100 1000 1024 3628800
20 4 400 8000 1048576 2.43E+18
30 5 900 27000 1.00E+08 2.65E+32
40 5 1600 64000 1.1E+12 8.16E+47
50 6 2500 125000 1.1E+15 3.04E+64
100 7 10000 1000000 1.3E+30 9.33E+157
200 8 40000 8000000 1.6E+60 >10^374