Complejidad de Algoritmos
¿Por qué algunos algoritmos se vuelven lentos con datos grandes? La notación Big-O describe cómo crece el tiempo de ejecución con la entrada. Aprende O(1), O(n), O(n²) y O(log n).
Renato Freitas
Actualizado el 5 de mayo de 2026
Por qué importa la eficiencia
Un algoritmo que ordena 10 números en 1 milisegundo puede tardar 16 minutos en ordenar 1 millón de números — si usa el algoritmo equivocado. Otro algoritmo puede hacer lo mismo en menos de 1 segundo. Esta diferencia no proviene del hardware, sino de la matemática detrás de cómo crece el tiempo de ejecución con el tamaño de la entrada.
Para entradas pequeñas, cualquier algoritmo parece rápido. La computadora moderna es tan veloz que las diferencias son imperceptibles. El problema aparece a escala: bases de datos con miles de millones de registros, imágenes con millones de píxeles, redes sociales con cientos de millones de usuarios. En esos contextos, elegir el algoritmo equivocado puede hacer que un producto sea inutilizable.
El análisis de complejidad da un lenguaje matemático para comparar algoritmos independientemente del hardware. En vez de medir segundos (que varían con el procesador), medimos cómo crece el número de operaciones en relación al tamaño n de la entrada.
🧮 Pruébalo tú mismo — CalcSim
¿Quieres más funciones? Descargar app CalcSim IA
La notación Big-O
Big-O es una notación matemática que describe el comportamiento de crecimiento de una función. O(f(n)) significa 'el tiempo de ejecución crece proporcionalmente a f(n) en el peor caso, ignorando constantes y términos menores'.
¿Por qué ignorar las constantes? Porque lo que importa es la tendencia de crecimiento. Un algoritmo que hace 100n operaciones y otro que hace 5n operaciones tienen la misma clase de complejidad O(n). Para n = 1 millón, ambos hacen entre 5 y 100 millones de operaciones — la diferencia es un factor constante, no una diferencia de escala.
Big-O describe el peor caso. La búsqueda lineal en una lista de n elementos puede encontrar el elemento en la primera posición (1 operación) o en la última (n operaciones). Big-O se preocupa por el peor caso: O(n).
Las cuatro complejidades más comunes
O(1) — constante: el tiempo de ejecución no depende del tamaño de la entrada. Acceder a un elemento de un array por índice es O(1): notas[42] siempre tarda lo mismo, sea el array de 10 o de 10 millones de elementos. Es la mejor complejidad posible.
O(n) — lineal: el tiempo crece proporcionalmente al tamaño de la entrada. La búsqueda lineal (recorrer todos los elementos hasta encontrar el buscado) es O(n). Si n se duplica, el tiempo máximo se duplica. Para n = 1 millón, hasta 1 millón de comparaciones.
O(n²) — cuadrática: común en algoritmos con dos bucles anidados. El Bubble Sort es O(n²): para cada uno de los n elementos, hace hasta n comparaciones. Si n se duplica, el tiempo se cuadruplica. Para n = 10.000, hasta 100 millones de operaciones — empieza a ser lento.
O(log n) — logarítmica: el tiempo crece muy despacio. La búsqueda binaria en una lista ordenada es O(log n): en cada paso, elimina la mitad de los elementos restantes. Para n = 1.000 millones, solo se necesitan aproximadamente 30 comparaciones (log₂ de 1.000.000.000 ≈ 30). Es prácticamente constante en la práctica.
- O(1): constante — acceso por índice, inserción al inicio de una tabla hash
- O(log n): logarítmica — búsqueda binaria, operaciones en árboles balanceados
- O(n): lineal — búsqueda lineal, recorrer una lista
- O(n log n): log-lineal — Merge Sort, Quicksort (caso promedio)
- O(n²): cuadrática — Bubble Sort, dos bucles anidados sobre n elementos
Búsqueda lineal versus búsqueda binaria
La búsqueda lineal verifica cada elemento del inicio al final. Es O(n) y funciona en cualquier lista, ordenada o no. La búsqueda binaria requiere que la lista esté ordenada, pero es mucho más eficiente: O(log n).
¿Cómo funciona la búsqueda binaria? Toma el elemento del medio de la lista. Si es el buscado, terminó. Si es mayor que el buscado, descarta la mitad derecha y repite en la mitad izquierda. Si es menor, descarta la mitad izquierda y repite en la mitad derecha. En cada paso, el espacio de búsqueda se reduce a la mitad.
Comparación práctica: buscar un nombre en una lista de 1 millón de personas ordenada alfabéticamente. Búsqueda lineal: hasta 1.000.000 comparaciones. Búsqueda binaria: hasta 20 comparaciones. Esta diferencia dramática explica por qué las bases de datos ordenan sus índices y por qué la ordenación es tan importante.
Implicaciones prácticas para software real
En el trabajo diario de desarrollo, el conocimiento de complejidad guía las elecciones de estructura de datos. Las tablas hash (diccionarios) ofrecen inserción y búsqueda O(1) en promedio — por eso son omnipresentes. Los árboles binarios balanceados ofrecen O(log n) para búsqueda, inserción y eliminación — usados en bases de datos y sistemas de archivos.
Un error común es llamar a una función O(n) dentro de un bucle O(n), creando inadvertidamente un algoritmo O(n²). Esto puede pasar desapercibido en pruebas con pocos datos y solo aparecer en producción, con datos reales.
La optimización prematura es un problema real: no intentes optimizar antes de identificar cuellos de botella. Pero conocer la complejidad de los algoritmos que usas es diferente de optimizar prematuramente — es tomar decisiones informadas desde el inicio del diseño.
Preguntas frecuentes
¿Big-O mide tiempo o memoria?
Big-O puede medir ambos. La complejidad de tiempo (temporal) describe cuántas operaciones ejecuta el algoritmo. La complejidad de espacio (espacial) describe cuánta memoria adicional se necesita en función del tamaño de la entrada. Generalmente, cuando se habla de Big-O sin especificación, se refiere a la complejidad temporal.
¿Qué es la complejidad del caso promedio versus el peor caso?
El peor caso es el escenario más desfavorable posible. El caso promedio es la expectativa sobre entradas aleatorias. Quicksort tiene peor caso O(n²) (cuando el pivote es siempre el menor o mayor elemento) pero caso promedio O(n log n). En la práctica, el caso promedio suele ser más relevante, pero el peor caso importa en sistemas críticos.
¿Un algoritmo O(n²) es siempre peor que uno O(n)?
Para n suficientemente grande, sí. Pero para n pequeño, un algoritmo O(n²) con constante baja puede ser más rápido que uno O(n) con constante alta. El Insertion Sort (O(n²)) frecuentemente es más rápido que el Merge Sort (O(n log n)) para listas con menos de 20–30 elementos, por tener menor sobrecarga.
¿Cómo saber la complejidad de un algoritmo que escribí?
Cuenta los bucles y cómo crecen con n. Un bucle simple sobre n elementos es O(n). Dos bucles anidados, cada uno sobre n elementos, es O(n²). Si en cada iteración divides el problema a la mitad (como en la búsqueda binaria), es O(log n). Ignora las constantes y los términos dominados por el mayor.
¿La complejidad importa para principiantes?
Entender los conceptos básicos sí — saber que dos bucles anidados son potencialmente problemáticos y que la búsqueda en una lista desordenada es más lenta que en una ordenada son conocimientos prácticos inmediatos. El análisis formal detallado puede aprenderse gradualmente conforme aumenta la experiencia.
¿Este artículo te fue útil?
Califica con estrellas para ayudarnos a mejorar el contenido.
Inicia sesión para calificar este artículo.
¿Aún tienes dudas?
El Profesor IA explica paso a paso
Haz una pregunta en lenguaje natural y recibe una explicación personalizada sobre Lógica de Programación — o cualquier otro tema.
¿Prefieres resolverlo en el móvil?
Descargar la app gratis →Sigue aprendiendo