El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Complejidad Algorítmica y Notación Big O

Siguiente ►
►

En la lección 01-02 comprobaste con el cronómetro que buscar una tarea en una lista de un millón de elementos tarda muchísimo más que buscarla en un índice. Pero los cronómetros tienen un problema: sus cifras dependen de tu ordenador, de tu versión de Python y hasta de qué más esté ejecutando tu máquina en ese momento. Necesitamos una forma de hablar de eficiencia que sea independiente de todo eso, y esa forma es la notación Big O. Es, sin exagerar, el vocabulario más importante del curso: a partir de aquí, cada operación de cada estructura vendrá etiquetada con su Big O. Dedícale a esta lección el tiempo que haga falta.

Contenido

  1. Complejidad temporal y espacial: contar en vez de cronometrar
  2. La notación Big O: qué significa exactamente
  3. Las clases habituales, con ejemplos en Python
  4. Comparativa: cuánto importa la clase de complejidad
  5. Mejor caso, peor caso y caso promedio
  6. Coste amortizado (mención breve)
  7. Midiendo TaskFlow con timeit: la teoría contra el cronómetro

Complejidad temporal y espacial: contar en vez de cronometrar

La idea central de la complejidad algorítmica es dejar de medir segundos y empezar a contar operaciones. En lugar de preguntar "¿cuánto tarda?", preguntamos: ¿cuántos pasos ejecuta el algoritmo en función del tamaño de la entrada, n?

  • Complejidad temporal: cuántas operaciones elementales (comparaciones, sumas, asignaciones...) realiza el algoritmo según crece n.
  • Complejidad espacial: cuánta memoria adicional necesita según crece n (sin contar la entrada misma).

Contemos pasos en la búsqueda secuencial de TaskFlow:

def buscar_en_lista(tareas, id_buscado):
    for tarea in tareas:              # se repite hasta n veces
        if tarea["id"] == id_buscado: # 1 comparación por vuelta
            return tarea
    return None

Si hay n tareas y la buscada está al final (o no está), el bucle da n vueltas con una comparación cada una: unas n operaciones. Si duplicamos las tareas, duplicamos el trabajo. Decimos que el tiempo crece linealmente con n. Su complejidad espacial, en cambio, es constante: use la lista el tamaño que use, la función solo necesita un puñado de variables auxiliares.

Este análisis tiene dos virtudes que el cronómetro no tiene:

  1. Es universal: n operaciones son n operaciones en tu portátil y en un servidor de producción.
  2. Predice el futuro: sabemos qué pasará con 10 millones de tareas sin necesidad de probarlo.

La notación Big O: qué significa exactamente

Al contar operaciones surgen detalles molestos: ¿la búsqueda hace exactamente n comparaciones, o n comparaciones más n accesos al campo "id" más 1 retorno, es decir, 2n + 1 operaciones? La respuesta de la notación Big O es: da igual. Lo único que importa es cómo crece el coste cuando n se hace grande.

Big O describe el orden de crecimiento del coste de un algoritmo cuando n tiende a valores grandes, ignorando constantes multiplicativas y términos menores.

Las dos reglas de simplificación:

  1. Ignora las constantes: 2n + 1 operaciones → O(n). Da lo mismo 2n que 5n: ambos se duplican al duplicar n, y eso es lo que Big O captura.
  2. Quédate con el término dominante: n² + 3n + 20 → O(n²). Cuando n = 1.000.000, el término n² aporta un billón de operaciones y el 3n apenas tres millones: los términos menores se vuelven irrelevantes.
def ejemplo(tareas):
    n = len(tareas)                # 1 operación
    print(tareas[0])               # 1 operación
    for t in tareas:               # n operaciones
        print(t["titulo"])
    for t1 in tareas:              # n * n = n² operaciones
        for t2 in tareas:
            if t1["id"] == t2["id"] and t1 is not t2:
                print("¡id duplicado!")

Coste total: 2 + n + n². Aplicando las dos reglas: O(n²). El bloque que domina es el doble bucle; para n grande, los demás ni se notan.

Un apunte de rigor: formalmente, Big O expresa una cota superior del crecimiento ("no crece más rápido que..."). En el uso cotidiano de la profesión —y en este curso— se emplea como sinónimo de "su coste crece como...", que es la interpretación práctica que necesitas.

Las clases habituales, con ejemplos en Python

Casi todo lo que analizaremos en el curso cae en cinco clases. Cada una, con un ejemplo real sobre las tareas de TaskFlow:

O(1) — constante

El coste no depende de n. Da igual que haya 10 tareas o 10 millones.

def primera_tarea(tareas):
    return tareas[0]          # acceder por índice no recorre nada

def total_tareas(tareas):
    return len(tareas)        # Python guarda el tamaño ya calculado

Acceder a tareas[0], a tareas[500_000] o preguntar len(tareas) cuesta lo mismo: un paso. Por qué el acceso por índice es O(1) lo entenderás a fondo en la lección 01-05.

O(log n) — logarítmica

El coste crece con el logaritmo de n: cada paso descarta la mitad de los datos. Duplicar n solo añade un paso más.

def buscar_binaria(tareas_ordenadas_por_id, id_buscado):
    """Requiere que las tareas estén ordenadas por id."""
    inicio, fin = 0, len(tareas_ordenadas_por_id) - 1
    while inicio <= fin:
        medio = (inicio + fin) // 2            # miramos el centro
        id_medio = tareas_ordenadas_por_id[medio]["id"]
        if id_medio == id_buscado:
            return tareas_ordenadas_por_id[medio]
        elif id_medio < id_buscado:
            inicio = medio + 1                 # descartamos la mitad izquierda
        else:
            fin = medio - 1                    # descartamos la mitad derecha
    return None

Cómo funciona: como las tareas están ordenadas por id, mirar la del centro nos dice en qué mitad está la buscada, y la otra mitad se descarta entera sin mirarla. Con un millón de elementos: 1.000.000 → 500.000 → 250.000 → ... → 1 en unos 20 pasos. Es el mismo truco que usas al buscar una palabra en un diccionario de papel: abres por el medio y descartas media obra de un vistazo.

O(n) — lineal

El coste crece en proporción directa a n: tocar cada elemento una vez.

def contar_pendientes(tareas):
    contador = 0
    for tarea in tareas:                  # n vueltas exactas
        if tarea["estado"] == "pendiente":
            contador += 1
    return contador

Nuestra vieja conocida buscar_en_lista también es O(n). Cualquier algoritmo que necesite mirar todos los datos al menos una vez es como mínimo O(n): no hay forma de contar las pendientes sin visitar cada tarea.

O(n log n) — casi lineal

La clase de los buenos algoritmos de ordenación. Intuición: hacer un trabajo O(log n) por cada uno de los n elementos, o dividir el problema por la mitad repetidamente ordenando en cada nivel.

tareas_ordenadas = sorted(tareas, key=lambda t: t["prioridad"])

El sorted de Python (algoritmo Timsort) es O(n log n). No lo implementaremos aquí; quédate con que ordenar bien cuesta O(n log n), sensiblemente más que recorrer (O(n)) pero muchísimo menos que comparar todo con todo (O(n²)).

O(n²) — cuadrática

El coste crece con el cuadrado de n: típicamente, un bucle dentro de otro, ambos sobre los datos. Duplicar n cuadruplica el trabajo.

def hay_titulos_duplicados(tareas):
    for i in range(len(tareas)):              # n vueltas
        for j in range(i + 1, len(tareas)):   # hasta n vueltas por cada i
            if tareas[i]["titulo"] == tareas[j]["titulo"]:
                return True
    return False

Cada tarea se compara con todas las siguientes: alrededor de n²/2 comparaciones, que por la regla de las constantes es O(n²). Con 1.000 tareas, medio millón de comparaciones; con un millón de tareas, quinientos mil millones. Las soluciones cuadráticas son aceptables solo con datos pequeños; detectarlas (y saber sustituirlas: este mismo problema es O(n) con un set) es una habilidad de entrevista clásica.

Existen clases peores —O(2ⁿ), O(n!)— propias de problemas de fuerza bruta; apenas nos las cruzaremos, pero conviene saber que existen y que son intratables incluso con n modestos.

Comparativa: cuánto importa la clase de complejidad

Números concretos: pasos aproximados que ejecuta cada clase según crece n (suponiendo, para traducir a tiempo, unos 10 millones de operaciones simples por segundo en Python):

n O(1) O(log n) O(n) O(n log n) O(n²)
10 1 3 10 33 100
1.000 1 10 1.000 10.000 1.000.000
1.000.000 1 20 10⁶ (~0,1 s) 2·10⁷ (~2 s) 10¹² (~28 horas)

Observa la última fila: con un millón de elementos, la diferencia entre O(n) y O(n²) es la diferencia entre una décima de segundo y más de un día. Y O(log n) sigue siendo, a efectos prácticos, instantáneo. Esta tabla explica por qué el experimento de la lección 01-02 dio los resultados que dio, y por qué la elección de estructura importa tanto: cada estructura ofrece sus operaciones con distintas clases de complejidad.

graph TB
    subgraph "Crecimiento del coste al aumentar n"
        A["O(1): plano"] --- B["O(log n): casi plano"]
        B --- C["O(n): recta"]
        C --- D["O(n log n): recta que se empina"]
        D --- E["O(n²): parábola — se dispara"]
    end

Y la tabla que usaremos como referencia durante todo el curso — el coste de las operaciones habituales sobre las estructuras nativas de Python:

Operación list dict / set
Acceso por índice lista[i] O(1) —
Acceso/inserción por clave — O(1) promedio
Buscar si contiene (in) O(n) O(1) promedio
Añadir al final (append/add) O(1) amortizado O(1) promedio
Insertar/borrar al principio o en medio O(n) —

Los apellidos "promedio" y "amortizado" se explican en los dos apartados siguientes.

Mejor caso, peor caso y caso promedio

Un mismo algoritmo puede costar distinto según la suerte de los datos. La búsqueda secuencial en TaskFlow:

  • Mejor caso: la tarea buscada es la primera → 1 comparación → O(1).
  • Peor caso: es la última o no existe → n comparaciones → O(n).
  • Caso promedio: si cualquier posición es igual de probable, unas n/2 comparaciones → O(n) (recuerda: las constantes como ½ se ignoran).
Escenario Qué describe Cuándo usarlo
Mejor caso El resultado con los datos más favorables Casi nunca: es información poco fiable
Peor caso La garantía máxima: nunca irá peor El estándar profesional por defecto
Caso promedio El comportamiento esperado con datos típicos Cuando el peor caso es raro y se conoce la distribución

Salvo que se diga lo contrario, cuando alguien da un Big O a secas se refiere al peor caso: es la garantía que permite dimensionar sistemas ("nunca tardará más que..."). El caso promedio importa cuando el peor caso es extraordinariamente improbable: el ejemplo estrella es el dict de Python, cuya búsqueda es O(1) en promedio pero puede degradarse en situaciones patológicas rarísimas (lo entenderás al estudiar colisiones en el módulo 5). Por eso la tabla anterior dice "O(1) promedio".

Coste amortizado (mención breve)

Queda un apellido por explicar: el append de list es "O(1) amortizado". El coste amortizado es el coste promediado sobre una secuencia larga de operaciones: casi todos los append son instantáneos, pero de tarde en tarde uno cuesta O(n) porque la lista debe reorganizarse por dentro; repartido ese coste ocasional entre todas las operaciones, sale a O(1) por operación.

De momento, quédate solo con la idea de "caro muy de vez en cuando, barato casi siempre, y en promedio constante". El porqué exacto —qué reorganización es esa y por qué sale a cuenta— es precisamente uno de los platos fuertes de la próxima lección (01-05), cuando veamos los arrays dinámicos.

Midiendo TaskFlow con timeit: la teoría contra el cronómetro

Cerremos el círculo: la teoría predice, y timeit verifica. Si buscar_en_lista es O(n), al multiplicar por 10 el número de tareas el tiempo debería multiplicarse por ~10. Comprobémoslo:

import timeit

def crear_tareas(n):
    return [{"id": i, "titulo": f"Tarea {i}"} for i in range(n)]

def buscar_en_lista(tareas, id_buscado):
    for tarea in tareas:
        if tarea["id"] == id_buscado:
            return tarea
    return None

for n in (10_000, 100_000, 1_000_000):
    tareas = crear_tareas(n)
    indice = {t["id"]: t for t in tareas}
    peor = n - 1   # peor caso: la última tarea

    t_lista = timeit.timeit(lambda: buscar_en_lista(tareas, peor), number=20)
    t_dict = timeit.timeit(lambda: indice.get(peor), number=20)

    print(f"n={n:>9} | lista: {t_lista:8.4f} s | dict: {t_dict:.6f} s")

Salida típica (tus cifras variarán; las proporciones no):

n=   10.000 | lista:   0,0059 s | dict: 0,000002 s
n=  100.000 | lista:   0,0601 s | dict: 0,000002 s
n=1.000.000 | lista:   0,6088 s | dict: 0,000002 s

Lectura del experimento:

  • La columna de la lista se multiplica por ~10 en cada fila, exactamente lo que predice O(n): coste proporcional a n.
  • La columna del dict no se mueve: O(1) en estado puro, confirmando la teoría del caso promedio.
  • Esto es lo que Big O te da y el cronómetro solo te insinúa: en la lección 01-02 vimos que pasaba; ahora sabemos cuánto y por qué, y podemos predecirlo para cualquier n sin ejecutar nada.

A partir de ahora, este será nuestro método con cada estructura: analizar el Big O de sus operaciones sobre el papel y, cuando aporte, confirmarlo con timeit.

Errores Comunes y Consejos

  • Creer que O(1) significa "rápido" y O(n) "lento". O(1) significa "coste que no depende de n", no "instantáneo": una operación O(1) puede ser lenta en términos absolutos, y una O(n) con n = 20 es despreciable. Big O habla de crecimiento, no de velocidad absoluta.
  • Olvidar los costes ocultos de Python. elemento in lista parece una operación, pero es O(n) por dentro; lista.insert(0, x) también. Un in sobre lista dentro de un bucle O(n) fabrica un O(n²) invisible: es el error de rendimiento más común en Python (lo viste en el ejercicio 2 de la lección 01-02).
  • Comparar algoritmos por el mejor caso. "Mi búsqueda a veces acierta a la primera" no dice nada útil. Analiza el peor caso por defecto y menciona el promedio solo cuando sepas justificarlo.
  • Ignorar la complejidad espacial. Crear un índice dict para buscar en O(1) gasta O(n) de memoria adicional. Casi siempre compensa, pero debes saber que estás pagando ese precio: tiempo y espacio se intercambian constantemente.
  • Consejo: cuando dudes del Big O de un código, cuenta los bucles anidados que dependen de n como primera aproximación (1 bucle → O(n), 2 anidados → O(n²)) y vigila las operaciones con coste oculto dentro de ellos.

Ejercicios

Ejercicio 1: clasificar fragmentos

Indica la complejidad temporal (Big O, peor caso) de cada fragmento y justifica en una frase:

# (a)
def ultima_tarea(tareas):
    return tareas[-1]

# (b)
def titulos_en_mayusculas(tareas):
    return [t["titulo"].upper() for t in tareas]

# (c)
def pares_de_tareas_conflictivas(tareas):
    pares = []
    for a in tareas:
        for b in tareas:
            if a["id"] != b["id"] and a["titulo"] == b["titulo"]:
                pares.append((a["id"], b["id"]))
    return pares

# (d)
def existe_id(tareas, id_buscado):
    return any(t["id"] == id_buscado for t in tareas)

Ejercicio 2: mejor, peor y promedio

Para la función existe_id del ejercicio anterior, describe su mejor caso, su peor caso y su caso promedio (suponiendo que el id buscado, cuando existe, está en una posición aleatoria uniforme). Da el Big O de cada uno.

Ejercicio 3: predicción y verificación empírica

hay_titulos_duplicados (vista en el apartado de O(n²)) compara cada tarea con las siguientes. (a) Predice: si con n = 1.000 tarda t segundos, ¿cuánto tardará aproximadamente con n = 2.000 y con n = 4.000? (b) Verifícalo con timeit usando tareas con títulos todos distintos (peor caso: no encuentra nada y compara todo). (c) Reescribe la función con un set para que sea O(n) y repite la medición.

Soluciones

Solución 1:

  • (a) O(1): el acceso por índice (aunque sea el último, [-1]) no recorre nada.
  • (b) O(n): la comprensión visita cada tarea exactamente una vez. (Nota: también gasta O(n) de espacio, porque crea una lista nueva.)
  • (c) O(n²): dos bucles anidados completos sobre las n tareas → n² comparaciones.
  • (d) O(n): any con un generador va comprobando tarea a tarea y se detiene al encontrar la primera coincidencia, pero en el peor caso (no existe) las recorre todas.

Solución 2:

  • Mejor caso: el id buscado está en la primera posición → 1 comparación → O(1).
  • Peor caso: el id no existe (o está el último) → n comparaciones → O(n).
  • Caso promedio: posición uniforme → n/2 comparaciones esperadas → O(n) (la constante ½ se descarta). Conclusión típica: mejor caso O(1), pero el algoritmo "es" O(n), porque por defecto hablamos del peor caso.

Solución 3:

(a) O(n²) implica que duplicar n cuadruplica el tiempo: con n = 2.000 tardará ~4t; con n = 4.000, ~16t.

(b) y (c):

import timeit

def hay_titulos_duplicados_v2(tareas):
    vistos = set()
    for t in tareas:                    # n vueltas
        if t["titulo"] in vistos:       # O(1) promedio sobre un set
            return True
        vistos.add(t["titulo"])         # O(1) promedio
    return False                        # total: O(n)

for n in (1_000, 2_000, 4_000):
    tareas = [{"id": i, "titulo": f"Tarea {i}"} for i in range(n)]
    t_v1 = timeit.timeit(lambda: hay_titulos_duplicados(tareas), number=3)
    t_v2 = timeit.timeit(lambda: hay_titulos_duplicados_v2(tareas), number=3)
    print(f"n={n}: O(n²) {t_v1:.3f} s | O(n) {t_v2:.5f} s")

Resultado típico: la versión cuadrática sigue la progresión ×4 predicha (por ejemplo 0,1 s → 0,4 s → 1,6 s), mientras la versión con set se limita a duplicarse (progresión ×2, lineal) y es cientos de veces más rápida ya con n = 4.000. La predicción teórica y la medición coinciden: eso es exactamente lo que Big O promete. (Coste del intercambio: la v2 usa O(n) de memoria extra para el conjunto vistos.)

Conclusión

Ya dominas el vocabulario central del curso: la complejidad temporal y espacial cuentan operaciones y memoria en función de n; la notación Big O captura el orden de crecimiento ignorando constantes y términos menores; las clases O(1), O(log n), O(n), O(n log n) y O(n²) cubren casi todo lo que analizaremos, con diferencias que van de "instantáneo" a "más de un día" con datos grandes; el análisis por defecto es el peor caso, reservando el promedio y el coste amortizado para cuando están justificados; y timeit permite confirmar empíricamente lo que la teoría predice.

Nos queda una deuda pendiente de esta lección: ¿por qué el acceso lista[i] es O(1)? ¿Y qué reorganización misteriosa hace que append sea solo O(1) amortizado? Las respuestas están un nivel más abajo, en cómo se organizan los datos físicamente en la memoria. Ese es el tema de la próxima lección: arrays y memoria, la base sobre la que se construye todo lo demás.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados