Complejidad computacional: definición y métricas de tiempo y espacio

Descubre la complejidad computacional: conceptos clave, análisis de tiempo y espacio, y métricas para optimizar algoritmos. Guía práctica y fácil de entender.

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.

¿Qué mide la complejidad?

La complejidad de un algoritmo se expresa principalmente en dos dimensiones:

• Complejidad temporal: cantidad de operaciones (o tiempo) que requiere el algoritmo en función del tamaño de la entrada.
• Complejidad espacial: cantidad de memoria adicional necesaria además de la entrada para ejecutar el algoritmo.

Notación asintótica

Para comparar algoritmos se usan notaciones que describen el comportamiento cuando el tamaño de la entrada n crece mucho:

• O grande (Big O): cota superior asintótica. Indica un límite superior del crecimiento (por ejemplo, O(n²)). Se usa frecuentemente para expresar el peor caso.
• Ω (Omega): cota inferior asintótica. Indica que el algoritmo necesita al menos tanto tiempo.
• Θ (Theta): cota ajustada: el crecimiento está acotado por arriba y por abajo por la misma función asintótica.
• o y ω: notaciones más finas (estrictas) para comparar crecimientos sin igualdad asintótica.

Caso peor, medio y mejor

Al analizar tiempo se suelen distinguir:

• Peor caso: tiempo máximo que puede tomar el algoritmo para cualquier entrada de tamaño n.
• Caso promedio: tiempo esperado si las entradas siguen algún modelo de distribución.
• Mejor caso: menor tiempo posible para entradas de tamaño n.

En práctica, el peor caso y el caso promedio son los más útiles para entender la robustez de un algoritmo.

Ejemplos comunes

• O(1): tiempo constante (acceso a un elemento por índice).
• O(log n): crecimiento logarítmico (búsqueda binaria en un arreglo ordenado).
• O(n): crecimiento lineal (búsqueda lineal).
• O(n log n): típicamente algoritmos eficientes de ordenación (mergesort, heapsort; quicksort promedio).
• O(n²): algoritmos cuadráticos (ordenación por inserción, burbuja en su versión simple).
• O(2^n), O(n!): complejidad exponencial o factorial, típica en problemas combinatorios y de fuerza bruta.

Clases de complejidad (breve)

Algunas clases importantes teóricas:

• P: problemas resolubles en tiempo polinómico por una máquina determinista.
• NP: problemas cuyas soluciones pueden verificarse en tiempo polinómico; incluye muchos problemas de decisión difíciles.
• NP-completo: subclase de NP a la que, si se encuentra un algoritmo polinómico para cualquiera de ellos, todos los problemas de NP serían polinomiales (es el núcleo de la famosa pregunta P vs NP).

Intercambio tiempo-espacio y otros conceptos

En muchos casos existe un trade-off entre tiempo y memoria: usar más memoria para almacenar resultados intermedios (memoización) puede reducir mucho el tiempo. Otros conceptos útiles:

• Complejidad amortizada: análisis del coste medio de una operación a lo largo de una secuencia (por ejemplo, inserciones en un vector dinámico).
• Algoritmos aleatorizados: usan azar para mejorar el tiempo promedio o simplificar el diseño.
• Algoritmos aproximados: devuelven soluciones cercanas a la óptima más rápido cuando encontrar la solución exacta es costoso.

Consideraciones prácticas

La notación asintótica ignora constantes y detalles de implementación: un algoritmo O(n) con una gran constante puede ser peor que un O(n log n) optimizado para tamaños prácticos. Además, factores como la localización de memoria, la caché, paralelismo y el hardware afectan el rendimiento real. Por eso conviene combinar:

• análisis asintótico para entender escalabilidad;
• perfiles y pruebas empíricas para comprender el comportamiento en datos reales;
• optimización de algoritmos y estructuras de datos adecuadas para el problema.

Cómo medir la complejidad

Para estimar complejidad:

• conteo de operaciones elementales (suma, comparación) como función de n;
• medición empírica mediante pruebas con entradas crecientes y ajuste de curvas;
• uso de análisis formal y reducción a problemas conocidos para clasificar su dificultad.

En resumen, la complejidad computacional proporciona las herramientas para categorizar algoritmos según su uso de tiempo y memoria, comparar alternativas y predecir su escalabilidad, lo que es esencial para diseñar soluciones eficientes en informática y al analizar los algoritmos en la práctica.

Búsqueda por letra