7 - Complejidad algorítmica (Big O)

El análisis de complejidad describe cómo crece el tiempo de ejecución o el consumo de memoria de un algoritmo a medida que aumentan los datos. Las estructuras de datos proporcionan operaciones con costos diferentes; cuantificarlos mediante notación Big O nos permite tomar decisiones informadas sin depender de hardware específico.

Esta sección introduce el vocabulario esencial, explica por qué importan los distintos tipos de análisis y muestra comparaciones concretas entre operaciones frecuentes. No buscamos reemplazar demostraciones formales, sino ofrecer una guía clara para interpretar tablas de complejidad y detectar oportunidades de mejora.

7. Complejidad algorítmica (Big O) - visión general

La complejidad se expresa en función del tamaño de entrada n. Es una herramienta predictiva: al estimar el comportamiento asintótico podemos proyectar cómo escalará el sistema cuando cambie la carga.

7.1 Objetivo del análisis Big-O

Big O resume el crecimiento máximo de un algoritmo ignorando constantes. Su objetivo es clasificar comportamientos para comparar implementaciones sin ejecutar cada variante en todos los escenarios posibles.

• Planeación: ayuda a validar si una solución cumplirá los acuerdos de nivel de servicio (SLA) cuando n se multiplique, es decir, los límites de tiempo de respuesta comprometidos con usuarios o clientes.
• Detección de cuellos: revela si la complejidad teórica es incompatible con el volumen de datos.
• Toma de decisiones: permite priorizar optimizaciones donde más impacto tendrán.

El análisis no intenta dar tiempos exactos, sino caracterizar el ritmo de crecimiento. Por eso dos algoritmos O(n) pueden diferir en segundos, pero ambos escalarán de forma linear.

7.2 Notaciones principales

Además de Big O, la teoría utiliza otras notaciones para brindar contextos distintos:

• O (mayor cota): describe el peor caso. Ejemplo: la búsqueda lineal es O(n) porque podría revisar todos los elementos.
• Ω (cota inferior): indica el mejor caso o el tiempo mínimo garantizado. La misma búsqueda es Ω(1) si encuentra la coincidencia en la primera posición.
• Θ (cota ajustada): se usa cuando el crecimiento superior e inferior coinciden; por ejemplo, insertar en una cola con memoria contigua es Θ(1).
• o y ω: describen cotas estrictas (crece menos o más que otra función) y se utilizan en demostraciones más formales.

Conocer estas variantes es útil para interpretar documentación de librerías y publicaciones académicas.

7.3 Relación entre estructura elegida y tiempo/espacio

La estructura impone los limites físicos del algoritmo. Un array contiguo ofrece accesos estables pero inserciones costosas; una lista enlazada sacrifica localidad de memoria para ganar flexibilidad. El mismo algoritmo puede pasar de O(1) a O(n) según la representación.

• Trade-off tiempo/espacio: usar tablas hash reduce el tiempo de búsqueda pero consume memoria extra en buckets.
• Reutilización de costos: preordenar datos conlleva un gasto inicial pero abarata operaciones futuras (por ejemplo, ordenaciones incrementales).
• Implementación concreta: dos estructuras con la misma complejidad asintótica pueden diferir por constantes significativas (p. ej., ArrayList vs LinkedList en Java).

7.4 Ejemplos simples

Veamos cómo cambian las complejidades cuando variamos la estructura o el algoritmo.

Acceso en array vs lista enlazada

Acceder a array[i] usa aritmética de punteros y se resuelve en O(1). En una lista enlazada debemos avanzar nodo por nodo hasta la posición deseada, lo que produce un costo O(n). Este contraste explica por qué las listas se reservan para escenarios donde importa más la modificación que la consulta aleatoria.

Búsqueda lineal vs búsqueda binaria

La búsqueda lineal compara cada elemento hasta encontrar la coincidencia (peor caso O(n)). La búsqueda binaria, en listas ordenadas, divide el espacio por la mitad en cada paso y alcanza un tiempo O(log n). A continuación se muestra una comparación en pseudocódigo:

def busqueda_lineal(datos, clave):
    for valor in datos:
        if valor == clave:
            return True
    return False  # O(n)

def busqueda_binaria(datos, clave):
    izq, der = 0, len(datos) - 1
    while izq <= der:
        medio = (izq + der) // 2
        if datos[medio] == clave:
            return True
        if clave < datos[medio]:
            der = medio - 1
        else:
            izq = medio + 1
    return False  # O(log n)

El requisito de tener los datos ordenados justifica el esfuerzo extra de ordenar previamente o mantener una estructura ordenada (como un árbol balanceado). En colecciones pequeñas la diferencia es mínima, pero con millones de elementos determina la viabilidad del sistema.