Inicio › Tecnología › Complejidad Algorítmica
Medida teórica de cómo crece el coste de un algoritmo, en tiempo de ejecución o en memoria consumida, a medida qué aumenta el tamaño de los datos de entrada, expresada habitualmente con la notación Big O. Un algoritmo O(n) tarda el doble si se duplican los datos, mientras qué uno O(n²) tarda cuatro veces más ante el mismo aumento, una diferencia insignificante con pocos datos pero determinante al trabajar con millones de registros. No depende del hardware ni del lenguaje usado, sino de la estructura lógica del algoritmo, lo qué permite comparar dos soluciones distintas de forma objetiva antes de implementarlas.
Es una forma de calcular cuánto se va a ralentizar un programa si le das muchos más datos, sin tener qué probarlo de verdad. Un algoritmo más eficiente no siempre gana con pocos datos, pero cuando los datos crecen mucho, la diferencia se nota muchísimo.
Al elegir cómo buscar un elemento dentro de una lista de un millón de registros, un desarrollador puede recorrerla entera una por una, complejidad O(n), o, si la lista está ordenada, usar búsqueda binaria dividiendo el espacio por la mitad en cada paso, complejidad O(log n); esta segunda opción encuentra el resultado en pocos pasos incluso con millones de elementos.
Describe el comportamiento del coste de un algoritmo, habitualmente en el peor caso, a medida qué crece el tamaño de la entrada, ignorando constantes y detalles de implementación: O(n) indica crecimiento lineal, O(n²) cuadrático y O(log n) logarítmico, mucho más lento.
No necesariamente; para conjuntos de datos pequeños, un algoritmo con mejor complejidad teórica puede tener un coste constante más alto qué lo haga en la práctica más lento qué uno más simple, conviene medir con datos reales antes de asumir la ventaja teórica.
No; también se analiza la complejidad espacial, cuánta memoria adicional necesita el algoritmo a medida qué crecen los datos, un factor tan importante como el tiempo en dispositivos con recursos limitados como sistemas embebidos.