Complejidad algorítmica y clases P/NP

Introducción a la complejidad algorítmica

La complejidad algorítmica mide la cantidad de recursos (tiempo y espacio) que un algoritmo necesita en función del tamaño de su entrada n. Entender estas medidas es esencial para diseñar soluciones eficientes y para comparar diferentes enfoques a un mismo problema.

Notaciones asintóticas: O, Ω y Θ

¿Qué es la notación O?

La notación O(f(n)) describe una cota superior del tiempo de ejecución en el peor caso. Indica que, para valores suficientemente grandes de n, el algoritmo no tardará más que c·f(n) para alguna constante c positiva.

Ejemplo típico: O(n²) significa que el número de operaciones crece como el cuadrado del tamaño de la entrada.

Notación Ω (cota inferior)

La notación Ω(f(n)) representa una cota inferior. Un algoritmo tiene complejidad Ω(f(n)) si, para entradas suficientemente grandes, necesita al menos c·f(n) operaciones.

Esta cota garantiza que no existe un algoritmo que sea más rápido que f(n) en el peor caso.

Notación Θ (cota ajustada)

Cuando un algoritmo está acotado tanto por arriba como por abajo con la misma función, usamos Θ(f(n)). En este caso, el crecimiento del algoritmo está ajustado a f(n).

Ejemplo: la búsqueda binaria tiene complejidad Θ(log n) porque su tiempo de ejecución está acotado superior e inferiormente por una función logarítmica.

Interpretando la notación O(log n)

Un algoritmo con complejidad O(log n) crece muy lentamente al aumentar n. Si duplicamos el tamaño de la entrada, el número de pasos aumenta en una constante adicional, no se duplica.

Esto se debe a que log(2n) = log n + log 2, y log 2 es una constante (≈0.693). Por lo tanto, el tiempo se incrementa en una cantidad fija, independientemente de cuán grande sea n.

Clases de complejidad: P vs NP

Los problemas de la clase P son aquellos que pueden resolverse en tiempo polinómico determinista. En cambio, los problemas de la clase NP son aquellos cuya solución puede verificarse en tiempo polinómico, aunque encontrarla pueda requerir más tiempo.

• P: "Problemas fáciles" – existen algoritmos eficientes que los resuelven.
• NP: "Problemas no determinísticos" – la verificación es rápida, pero la búsqueda puede ser costosa.

Una pregunta central en teoría de la computación es si P = NP. La mayoría de los investigadores creen que P ≠ NP, lo que implica que existen problemas cuya verificación es fácil pero cuya solución es intrínsecamente difícil.

Problemas NP‑completos

Un problema es NP‑completo si pertenece a NP y es al menos tan difícil como cualquier otro problema de NP. Bajo la hipótesis P ≠ NP, ningún algoritmo polinómico puede resolver todos los problemas NP‑completos.

Ejemplo clásico: el problema del viajante de comercio (TSP). La versión de fuerza bruta que prueba todas las permutaciones tiene complejidad O(n!), que es exponencial.

Complejidad exponencial y casos típicos

Los algoritmos con complejidad exponencial, como O(2ⁿ) o O(n!), crecen extremadamente rápido y se vuelven inviables incluso para tamaños moderados de entrada. Un caso típico es el algoritmo de fuerza bruta para el TSP, donde el número de rutas posibles es (n‑1)!/2.

En contraste, algoritmos como la búsqueda binaria (O(log n)) o el algoritmo de Euclides para el máximo común divisor (O(log n)) son muy eficientes.

La constante oculta en la notación O(f(n))

La "constante oculta" es el factor multiplicativo c que acompaña a la función f(n). Aunque no afecta la clasificación asintótica, sí influye en el rendimiento práctico. Dos algoritmos con la misma notación O(n²) pueden diferir significativamente en tiempo real debido a distintas constantes ocultas.

En la práctica, al comparar implementaciones, es importante considerar tanto la notación como la constante implícita.

Comparación entre O(n²) y O(n log n)

Para valores muy grandes de n, la complejidad O(n log n) es más eficiente que O(n²). Aunque para n pequeños la diferencia puede ser marginal, a medida que n crece, el término cuadrático domina y el algoritmo O(n²) se vuelve mucho más lento.

Esta observación guía la elección de algoritmos en aplicaciones de gran escala, como ordenamiento de bases de datos (merge‑sort O(n log n)) frente a algoritmos de inserción (O(n²)) para listas pequeñas.

Propiedades de una cota inferior Ω

Para que una función g(n) sea una cota inferior Ω de la complejidad de un algoritmo, debe acotar por debajo el número de operaciones para entradas suficientemente grandes. Formalmente, existen constantes c > 0 y n₀ tal que c·g(n) ≤ T(n) para todo n ≥ n₀, donde T(n) es el tiempo real del algoritmo.

Esta propiedad garantiza que el algoritmo no puede ser más rápido que g(n) en el peor caso.

Resumen de conceptos clave

• O(f(n)): cota superior (peor caso).
• Ω(f(n)): cota inferior (mejor caso).
• Θ(f(n)): cota ajustada (ambas).
• En P los problemas se resuelven en tiempo polinómico; en NP la solución se verifica en tiempo polinómico.
• Los problemas NP‑completos son los más difíciles dentro de NP y, bajo P ≠ NP, no tienen algoritmo polinómico.
• La constante oculta no cambia la clasificación asintótica, pero sí el rendimiento práctico.
• Para n grande, O(n log n) supera a O(n²).

Dominar estas nociones permite elegir y diseñar algoritmos que escalen adecuadamente, optimizando recursos y tiempo de cómputo.