Teoría de la complejidad computacional
La teoría de la complejidad computacional forma parte de la informática. Examina los algoritmos y trata de decir cuántos pasos o cuánta memoria necesita un ordenador para realizar un determinado algoritmo. Muy a menudo, los algoritmos que utilizan menos pasos usan más memoria (o al revés: si hay menos memoria disponible, se necesitan más pasos para hacerlo). Muchos algoritmos interesantes llevan un número de pasos que depende del tamaño del problema.
Diferentes clases de complejidad
Complejidad constante
La teoría de la complejidad también examina cómo cambia un problema si se hace para más elementos. Un problema de clase de complejidad constante es la única clase en la que esto no es cierto. Un problema de complejidad constante tarda el mismo número de pasos en completarse sin importar el tamaño de la entrada o el número de elementos sobre los que se calcula. La transmisión de un mensaje puede considerarse un problema de complejidad constante. No importa cuántas personas necesiten recibir un mensaje, todas pueden escuchar una sola emisión sin necesidad de emisiones adicionales.
Complejidad lineal
Cortar el césped puede considerarse un problema de complejidad lineal. Cortar un área que es el doble de grande que la original lleva el doble de tiempo.
Complejidad cuadrática
Supongamos que quieres saber cuáles de tus amigos se conocen entre sí. Tienes que preguntar a cada par de amigos si se conocen entre sí. Si tienes el doble de amigos que otra persona, tienes que hacer cuatro veces más preguntas para averiguar a quién conoce cada uno. Se dice que los problemas que tardan cuatro veces más cuando el tamaño del problema se duplica tienen una complejidad cuadrática.
Complejidad logarítmica
Esta es a menudo la complejidad de los problemas que implican buscar cosas, como encontrar una palabra en un diccionario. Si el diccionario es el doble de grande, contiene el doble de palabras que el original para comparar. Buscar algo sólo llevará un paso más. El algoritmo para hacer búsquedas es sencillo. La palabra en el centro del diccionario estará antes o después del término que hay que buscar, si las palabras no coinciden. Si está antes, el término debe estar en la segunda mitad del diccionario. Si está después de la palabra, tiene que estar en la primera mitad. De este modo, el espacio del problema se reduce a la mitad en cada paso, hasta que se encuentra la palabra o la definición. Esto se conoce generalmente como complejidad logarítmica
Complejidad exponencial
Hay problemas que crecen muy rápido. Uno de estos problemas se conoce como el problema del vendedor ambulante. Un vendedor tiene que hacer un recorrido por un determinado número de ciudades. Cada ciudad debe ser visitada sólo una vez, la distancia (o el coste) del viaje debe ser mínimo, y el vendedor debe terminar donde empezó. Este problema tiene una complejidad exponencial. Hay que tener en cuenta n posibilidades factoriales. Si se añade una ciudad (de n a n+1) se multiplicará el número de posibilidades por (n+1). La mayoría de los problemas interesantes tienen esta complejidad.
