La complejidad computacional es el área de la informática que estudia los recursos necesarios para resolver un problema mediante un algoritmo.
Los dos recursos que normalmente se analizan son:
- Tiempo: cuánto aumenta el número de operaciones necesarias.
- Espacio: cuánta memoria necesita el algoritmo.
El objetivo no es simplemente medir cuántos segundos tarda un programa en una computadora determinada, sino estudiar cómo aumenta el costo computacional cuando crece el tamaño de los datos de entrada.
Por ejemplo, si necesitamos buscar un nombre entre 100 registros, prácticamente cualquier método puede parecer rápido. Pero si debemos buscar entre millones de registros, la diferencia entre un algoritmo eficiente y uno ineficiente puede ser enorme.
Por eso, la complejidad computacional permite comparar algoritmos y comprender cuáles pueden seguir siendo viables cuando aumenta la cantidad de información.
¿Para qué sirve la complejidad computacional?
Analizar la complejidad permite anticipar cómo se comportará un algoritmo antes de utilizarlo con grandes cantidades de datos.
Sirve principalmente para:
- Comparar diferentes algoritmos que resuelven un mismo problema.
- Estimar cómo crecerá el tiempo de ejecución.
- Analizar el consumo de memoria.
- Identificar algoritmos que pueden volverse demasiado costosos.
- Elegir estructuras de datos y estrategias más eficientes.
- Comprender los límites de determinados problemas computacionales.
Esto es importante porque dos algoritmos pueden producir exactamente el mismo resultado y, aun así, necesitar cantidades de recursos completamente diferentes.
¿Qué es el costo computacional?
El costo computacional representa la cantidad de recursos necesarios para ejecutar un algoritmo.
Este costo puede analizarse principalmente desde dos perspectivas: tiempo y espacio.
Por ejemplo, supongamos que tenemos dos algoritmos capaces de encontrar un elemento dentro de una colección.
El primero necesita revisar prácticamente todos los elementos. El segundo puede descartar una parte importante de los datos en cada paso.
Aunque ambos resuelvan el mismo problema, su costo computacional puede ser muy diferente cuando aumenta el tamaño de la entrada.
Por eso, al analizar algoritmos no basta con comprobar que funcionan: también interesa conocer qué tan eficientemente utilizan los recursos disponibles.
Complejidad temporal
La complejidad temporal describe cómo aumenta la cantidad de operaciones necesarias para ejecutar un algoritmo conforme crece el tamaño de la entrada.
No debe interpretarse literalmente como una cantidad determinada de segundos.
El tiempo real depende de factores como:
- Procesador.
- Lenguaje de programación.
- Implementación.
- Sistema operativo.
- Hardware disponible.
La complejidad temporal permite abstraerse de esas diferencias y estudiar el crecimiento del algoritmo.
Ejemplo de complejidad O(n)
Consideremos una búsqueda lineal:
function buscarNumero($numeros, $objetivo) {
foreach ($numeros as $numero) {
if ($numero === $objetivo) {
return true;
}
}
return false;
}En el peor caso, el algoritmo debe revisar todos los elementos.
Si tenemos n elementos, puede realizar aproximadamente n comprobaciones.
Por eso hablamos de una complejidad:
O(n)
Si duplicamos aproximadamente la cantidad de elementos, también puede duplicarse la cantidad de operaciones necesarias.
Complejidad espacial
La complejidad espacial estudia cómo aumenta la memoria utilizada por un algoritmo conforme crece el tamaño de los datos de entrada.
Un algoritmo puede ser rápido pero necesitar mucha memoria, mientras que otro puede utilizar menos memoria a cambio de realizar más operaciones.
Por ejemplo, si procesamos una colección sin crear estructuras adicionales cuyo tamaño dependa de la entrada, podemos tener un consumo adicional de memoria cercano a:
O(1)
Si creamos otra colección que almacena una copia de los n elementos originales, el espacio adicional puede crecer como:
O(n)
Por eso, al evaluar un algoritmo conviene considerar tanto su complejidad temporal como espacial.
¿Qué es la notación Big O?
La notación Big O se utiliza para describir una cota superior del crecimiento de los recursos requeridos por un algoritmo.
Permite expresar cómo cambia su comportamiento cuando aumenta n, donde n representa normalmente el tamaño de la entrada.
Algunas complejidades habituales son:
| Complejidad | Nombre | Ejemplo |
|---|---|---|
| O(1) | Constante | Acceder a una posición conocida de un arreglo |
| O(log n) | Logarítmica | Búsqueda binaria |
| O(n) | Lineal | Recorrer una lista |
| O(n log n) | Lineal-logarítmica | Mergesort |
| O(n²) | Cuadrática | Dos recorridos anidados de n elementos |
| O(2ⁿ) | Exponencial | Algunos algoritmos exhaustivos |
| O(n!) | Factorial | Explorar todas las permutaciones |
En general, las diferencias entre estas funciones se vuelven mucho más importantes conforme aumenta n.
Ejemplo: O(n) frente a O(n²)
Supongamos que tenemos 10 elementos.
Un algoritmo O(n) podría necesitar aproximadamente 10 operaciones relacionadas con el tamaño de entrada.
Uno O(n²) podría necesitar alrededor de:
10 × 10 = 100
Ahora aumentemos la entrada a 1.000 elementos.
El crecimiento aproximado sería:
- O(n): 1.000
- O(n²): 1.000.000
Este ejemplo simplificado muestra por qué la complejidad puede resultar mucho más importante que pequeñas diferencias de rendimiento observadas con pocos datos.
¿Cómo calcular la complejidad de un algoritmo?
Para realizar un análisis básico podemos observar cuántas veces se ejecutan las operaciones principales en función del tamaño de entrada.
Consideremos:
for i = 1 to n
print(i)El ciclo se ejecuta n veces.
Por tanto:
O(n)
Ahora agreguemos otro ciclo:
for i = 1 to n
for j = 1 to n
print(i, j)Por cada ejecución del primer ciclo se realizan n ejecuciones del segundo.
Tenemos aproximadamente:
n × n = n²
Por tanto, su complejidad es:
O(n²)
Este análisis se concentra en el crecimiento y normalmente ignora constantes y términos menos significativos.
Por ejemplo:
3n² + 5n + 10
se expresa como:
O(n²)
porque n² es el término dominante cuando n aumenta.
Complejidad de algoritmos comunes
La complejidad puede verse fácilmente al comparar algoritmos conocidos.
Búsqueda lineal
La búsqueda lineal revisa los elementos uno por uno hasta encontrar el valor buscado.
En el peor caso:
O(n)
Búsqueda binaria
Si los datos están ordenados, la búsqueda binaria divide repetidamente el espacio de búsqueda.
Su complejidad temporal es:
O(log n)
Por eso puede resultar considerablemente más eficiente que recorrer todos los elementos cuando trabajamos con colecciones grandes y ordenadas.
Ordenación por inserción
Insertion Sort tiene una complejidad de peor caso de:
O(n²)
Puede ser útil para colecciones pequeñas o casi ordenadas, pero pierde eficiencia al crecer la entrada.
Mergesort
Mergesort divide los datos y posteriormente combina los resultados ordenados.
Su complejidad temporal es:
O(n log n)
Quicksort
Quicksort también utiliza una estrategia de división del problema.
Su rendimiento promedio es:
O(n log n)
aunque su peor caso puede llegar a:
O(n²)
La implementación y la elección del pivote influyen en su comportamiento.
Análisis asintótico: O, Ω y Θ
Big O no es la única notación utilizada en el análisis asintótico.
O grande
O expresa una cota superior asintótica.
Por ejemplo:
O(n²)
indica que el crecimiento está acotado superiormente por una función cuadrática, salvo factores constantes para entradas suficientemente grandes.
Omega
Ω representa una cota inferior asintótica.
Permite describir un crecimiento mínimo.
Theta
Θ representa una cota ajustada cuando podemos establecer tanto una cota superior como inferior del mismo orden.
Estas notaciones permiten describir matemáticamente el comportamiento de los algoritmos conforme aumenta el tamaño de entrada.
Complejidad de un algoritmo vs. complejidad de un problema
Aunque suelen relacionarse, no significan exactamente lo mismo.
La complejidad de un algoritmo estudia los recursos utilizados por un procedimiento concreto.
La complejidad de un problema analiza los recursos necesarios para resolver una categoría completa de problemas.
Por ejemplo, podemos estudiar cuánto tarda un algoritmo específico de ordenación, pero la teoría de complejidad también busca determinar qué tan difícil es resolver determinados problemas independientemente de una implementación concreta.
Esta distinción conduce a las llamadas clases de complejidad.
Clases de complejidad
Las clases de complejidad agrupan problemas según los recursos computacionales necesarios para resolverlos o verificar sus soluciones bajo modelos determinados de computación.
Entre las más conocidas están P y NP.
Clase P
P contiene problemas de decisión que pueden resolverse mediante un algoritmo determinista en tiempo polinómico.
De manera simplificada, son problemas para los que conocemos algoritmos cuyo tiempo de ejecución está limitado por una función polinómica del tamaño de entrada.
Clase NP
NP contiene problemas de decisión cuyas soluciones propuestas pueden verificarse en tiempo polinómico.
Una confusión frecuente consiste en interpretar NP como «no polinómico».
No significa eso.
El nombre procede de nondeterministic polynomial time.
¿Qué significa P vs. NP?
Una de las preguntas fundamentales de la teoría de la complejidad es:
¿P = NP?
Sabemos que:
P ⊆ NP
porque una solución que podemos obtener en tiempo polinómico también puede verificarse en tiempo polinómico.
La cuestión es determinar si todos los problemas de NP también pertenecen a P.
Es decir, si todo problema cuya solución puede verificarse eficientemente también puede resolverse eficientemente.
Actualmente no existe una demostración aceptada de que P = NP ni de que P ≠ NP.
¿Qué es un problema NP-completo?
Los problemas NP-completos son problemas que:
- Pertenecen a NP.
- Son NP-hard, es decir, cualquier problema de NP puede reducirse a ellos en tiempo polinómico.
Esta característica los convierte en una parte fundamental del estudio de la complejidad.
Si se encontrara un algoritmo de tiempo polinómico para cualquier problema NP-completo, entonces todos los problemas pertenecientes a NP podrían resolverse en tiempo polinómico y se demostraría que:
P = NP
Un ejemplo clásico de problema NP-completo es el problema de satisfacibilidad booleana, conocido como SAT.
¿Qué significa NP-hard?
Un problema NP-hard es al menos tan difícil, bajo reducciones apropiadas, como los problemas pertenecientes a NP.
Sin embargo, un problema NP-hard no necesariamente pertenece a NP.
Esta es una diferencia importante:
- NP-completo: pertenece a NP y además es NP-hard.
- NP-hard: no tiene que pertenecer necesariamente a NP.
Computabilidad y complejidad: ¿cuál es la diferencia?
La computabilidad y la complejidad computacional estudian preguntas relacionadas, pero diferentes.
La computabilidad pregunta principalmente:
¿Puede resolverse este problema mediante un algoritmo?
La complejidad pregunta:
Si puede resolverse, ¿qué recursos computacionales necesitamos?
Por tanto, primero podemos preguntarnos si un problema es computable y posteriormente analizar qué tan costoso resulta resolverlo.
Esta diferencia es importante porque existen problemas que no pueden resolverse algorítmicamente en general, mientras que otros sí pueden resolverse pero requieren una cantidad considerable de recursos.
¿Por qué es importante la complejidad computacional?
La complejidad computacional permite entender mejor las limitaciones y posibilidades de los algoritmos.
Tiene aplicaciones en áreas como:
- Diseño y análisis de algoritmos.
- Bases de datos.
- Inteligencia artificial.
- Criptografía.
- Optimización.
- Procesamiento de grandes cantidades de información.
- Redes y sistemas distribuidos.
- Desarrollo de software.
Por ejemplo, cuando una aplicación debe procesar millones de registros, elegir una estructura de datos o algoritmo adecuado puede reducir significativamente la cantidad de operaciones necesarias.
En sistemas a gran escala, esas diferencias también pueden repercutir en consumo de memoria, infraestructura y costos computacionales.
¿Cómo reducir el costo computacional de un algoritmo?
No existe una técnica universal, pero algunas estrategias habituales son:
- Eliminar operaciones innecesarias.
- Evitar cálculos repetidos.
- Elegir estructuras de datos apropiadas.
- Utilizar algoritmos con mejor comportamiento asintótico cuando sea posible.
- Almacenar resultados previamente calculados cuando resulte conveniente.
- Dividir problemas grandes en problemas más pequeños.
- Analizar los casos que provocan mayor consumo de recursos.
Sin embargo, reducir la complejidad temporal puede requerir utilizar más memoria y viceversa.
Por eso, la optimización suele implicar encontrar un equilibrio adecuado para las necesidades del sistema.
Preguntas frecuentes sobre complejidad computacional
¿Qué es la complejidad computacional?
Es el estudio de los recursos necesarios para resolver problemas computacionales, principalmente tiempo de ejecución y espacio de memoria, en función del tamaño de la entrada.
¿Qué es la complejidad de un algoritmo?
Es una medida del crecimiento de los recursos que necesita un algoritmo conforme aumenta el tamaño de los datos que procesa.
¿Qué es el costo computacional?
Es la cantidad de recursos utilizados para ejecutar un algoritmo o resolver un problema. Puede incluir tiempo de procesamiento, memoria y otros recursos dependiendo del análisis realizado.
¿Cuál es la diferencia entre complejidad temporal y espacial?
La complejidad temporal estudia cómo aumenta el número de operaciones necesarias, mientras que la complejidad espacial analiza cómo aumenta el uso de memoria.
¿Qué significa O(1)?
Significa que el número de operaciones considerado permanece acotado independientemente del tamaño de entrada.
¿Qué significa O(n)?
Significa que el crecimiento es lineal respecto al tamaño de entrada.
¿Qué significa O(n²)?
Representa un crecimiento cuadrático. Si n aumenta considerablemente, el número de operaciones puede crecer mucho más rápido que en un algoritmo lineal.
¿Big O mide segundos?
No. Big O describe crecimiento asintótico, no una duración concreta. Dos implementaciones con la misma complejidad pueden tardar tiempos diferentes en la práctica.
¿NP significa «no polinómico»?
No. NP significa nondeterministic polynomial time. Incluye problemas cuyas soluciones pueden verificarse en tiempo polinómico.
¿P es igual a NP?
No se sabe. Determinar si P = NP continúa siendo un problema abierto de la informática teórica.
¿Qué diferencia existe entre computabilidad y complejidad?
La computabilidad estudia si un problema puede resolverse mediante un algoritmo. La complejidad estudia los recursos necesarios para resolver problemas computables.
En resumen
La complejidad computacional permite estudiar cuánto aumentan los recursos necesarios para resolver un problema conforme crece su tamaño.
Conceptos como complejidad temporal, complejidad espacial, costo computacional, Big O y clases de complejidad permiten comparar algoritmos y comprender los límites de diferentes problemas.
Para un desarrollador, entender estos conceptos ayuda a elegir mejores algoritmos y estructuras de datos. Para la informática teórica, permite estudiar preguntas mucho más profundas sobre qué problemas pueden resolverse eficientemente y cuáles presentan dificultades fundamentales.
También te puede interesar...
