Significado de Complejidad algorítmica
Sustantivo femenino compuesto. «Complejidad», del latín complexitas; «algorítmica», adjetivo derivado de algoritmo. Calco parcial del inglés algorithmic complexity.
La complejidad algorítmica es una medida de cuánto tiempo de ejecución o memoria necesita un algoritmo en función del tamaño de los datos que procesa, sin depender de un ordenador concreto.
Se expresa mediante la notación Big O, que describe cómo crece ese coste a medida que aumenta la cantidad de datos, en lugar de dar un tiempo exacto en segundos.
Qué es la complejidad algorítmica
Dos algoritmos pueden resolver exactamente el mismo problema y dar el mismo resultado, pero tardar tiempos muy distintos si el conjunto de datos es grande. La complejidad algorítmica compara esa diferencia de forma independiente del ordenador en el que se ejecuten, contando cuántas operaciones básicas realiza el algoritmo según crece el número de elementos que recibe.
No mide el tiempo real en segundos, porque ese tiempo depende del procesador, de otros programas en marcha y de muchos factores ajenos al algoritmo. En su lugar, describe una tendencia: si al doblar el tamaño de los datos el algoritmo tarda el doble, el cuádruple o mucho más que eso.
La estudia el análisis de algoritmos dentro de las ciencias de la computación. Suele distinguirse entre complejidad temporal, referida al número de operaciones, y complejidad espacial, referida a la memoria adicional que el algoritmo necesita mientras se ejecuta.
Origen de la expresión complejidad algorítmica
«Complejidad» procede del latín complexitas, derivado de complecti, «abarcar, enlazar». «Algorítmica» se forma sobre «algoritmo», del latín medieval algorismus. La notación que la representa, conocida como «Big O» (de la letra griega ómicron), se popularizó como forma abreviada de comparar algoritmos sin calcular tiempos exactos.
El estudio formal de cuánto tardan los algoritmos según el tamaño de la entrada se desarrolló junto con la teoría de la computación a lo largo del siglo XX, a medida que los problemas que se intentaba resolver con ordenadores crecían en escala. Hoy es un contenido básico en la formación de cualquier persona que programe de forma profesional.
Tipos de complejidad algorítmica
| Notación | Cómo crece el coste | Ejemplo |
|---|---|---|
| O(1) | Constante: no depende del tamaño de los datos. | Acceder a un elemento de una lista conociendo su posición exacta. |
| O(log n) | Logarítmica: crece muy despacio al aumentar los datos. | Buscar un nombre en una lista ya ordenada, descartando la mitad en cada paso. |
| O(n) | Lineal: el coste crece en la misma proporción que los datos. | Revisar cada elemento de una lista una sola vez. |
| O(n²) | Cuadrática: el coste crece mucho más rápido que los datos. | Comparar cada elemento de una lista con todos los demás. |
Al comparar algoritmos según su complejidad, interesa sobre todo cómo se comportan con conjuntos de datos grandes: una diferencia pequeña con pocos datos puede volverse enorme cuando el número de elementos se multiplica.
Ejemplos de uso de complejidad algorítmica
El profesor pidió calcular la complejidad algorítmica de dos soluciones distintas al mismo ejercicio de programación.
Cambiar la estructura de datos redujo la complejidad algorítmica de la búsqueda, y la aplicación empezó a responder mucho más rápido.
En la entrevista técnica le preguntaron por la complejidad algorítmica, en tiempo y en memoria, de la función que acababa de escribir.
El manual explica la complejidad algorítmica de los algoritmos de ordenación más habituales mediante la notación Big O.
Sinónimos y palabras relacionadas
Sinónimos: eficiencia algorítmica, coste computacional (con un matiz algo más amplio).
Antónimos: no tiene antónimos propiamente dichos.
No es lo mismo que:
- Tiempo de ejecución: es una medida concreta, en segundos, en un ordenador determinado; la complejidad algorítmica describe la tendencia de crecimiento, independiente de la máquina.
- Algoritmo: es el procedimiento en sí; la complejidad algorítmica es una propiedad que se mide sobre ese procedimiento, no el procedimiento mismo.
- Rendimiento: es un concepto más amplio que incluye factores prácticos como el hardware o la carga del sistema; la complejidad algorítmica se centra solo en el comportamiento teórico del algoritmo.
Preguntas frecuentes sobre complejidad algorítmica
¿Qué es la notación Big O?
Es la forma habitual de expresar la complejidad algorítmica: describe cómo crece el número de operaciones de un algoritmo a medida que aumenta el tamaño de los datos, sin dar un tiempo exacto en segundos.
¿Por qué importa la complejidad algorítmica si un ordenador es muy rápido?
Porque con conjuntos de datos pequeños casi cualquier algoritmo parece rápido, pero al crecer el volumen de datos, uno con peor complejidad puede tardar muchísimo más que otro, por potente que sea el ordenador que lo ejecute.
¿Es lo mismo complejidad temporal que complejidad espacial?
No: la temporal mide cuántas operaciones realiza el algoritmo según crecen los datos, y la espacial mide cuánta memoria adicional necesita mientras se ejecuta. Un algoritmo puede ser rápido en tiempo y costoso en memoria, o al revés.