Cómo calcular la complejidad de un algoritmo: bucles, recursión y ejemplos de código

La notación asintótica dice cómo se expresa el coste de un algoritmo. Este tema es la parte práctica: cómo se mira un código y se calcula su complejidad. Con unas pocas reglas para bucles, llamadas y recursión se analiza casi cualquier programa, y se puede predecir si tardará un milisegundo o un año con un millón de datos.

Lo que vas a aprender

Qué cuenta como operación elemental.
Las reglas para secuencias, condicionales y bucles.
Los bucles anidados, dependientes y logarítmicos.
Cómo analizar la recursión.
El coste oculto de las operaciones de las estructuras de datos.
La complejidad espacial.

Fundamentos teóricos

Operaciones elementales

Las que tardan un tiempo constante,

O(1)

: asignaciones, operaciones aritméticas, comparaciones, acceso a un elemento de un array por índice, llamar a una función (sin contar lo que hace dentro).

Reglas básicas

Estructura	Coste
Secuencia de bloques	La suma, que se queda con el mayor: $O(f) + O(g) = O(\max(f, g))$
`if` / `else`	El coste de la condición más el de la rama más cara (peor caso)
Bucle de $n$ vueltas con cuerpo $O(g)$	$O(n\cdot g)$
Bucles anidados independientes	El producto de las vueltas
Llamada a función	El coste de la función

Bucles típicos

Bucle	Vueltas	Coste
`for i in range(n)`	$n$	$O(n)$
`for i in range(n): for j in range(n)`	$n^2$	$O(n^2)$
`for i in range(n): for j in range(i)`	$0 + 1 + \cdots + (n-1) = \frac{n(n-1)}{2}$	$O(n^2)$
`while i < n: i *= 2`	$\log_2 n$	$O(\log n)$
`while n > 0: n //= 2`	$\log_2 n$	$O(\log n)$
`for i in range(n): j = 1; while j < n: j *= 2`	$n\log n$	$O(n\log n)$
`for i in range(100)`	100	$O(1)$ : no depende de $n$

La clave de los bucles logarítmicos: la variable se multiplica o divide por una constante en cada vuelta, en lugar de sumar.

Recursión

Se escribe una recurrencia con el coste de cada llamada y el de las llamadas que hace:

Código	Recurrencia	Coste
Recorrer una lista recursivamente	$T(n) = T(n-1) + O(1)$	$O(n)$
Búsqueda binaria	$T(n) = T(n/2) + O(1)$	$O(\log n)$
Merge sort	$T(n) = 2T(n/2) + O(n)$	$O(n\log n)$
Fibonacci ingenuo	$T(n) = T(n-1) + T(n-2) + O(1)$	$O(\varphi^n) \approx O(1{,}618^n)$
Todos los subconjuntos	$T(n) = 2T(n-1) + O(1)$	$O(2^n)$

Las del tipo

aT(n/b) + O(n^k)

se resuelven con el teorema maestro (ver divide y vencerás).

El coste oculto de las estructuras de datos

Una sola línea puede esconder un bucle:

Operación en Python	Lista	Diccionario / conjunto
Acceso por índice o clave	$O(1)$	$O(1)$ de media
`x in estructura`	$O(n)$	$O(1)$ de media
Añadir al final / insertar	$O(1)$ amortizado	$O(1)$ de media
Insertar o borrar al principio	$O(n)$	—
`sorted(lista)`	$O(n\log n)$	—
Copiar, `lista[a:b]`, `+`	$O(k)$ , el tamaño copiado	—
`min`, `max`, `sum`, `count`	$O(n)$	—

Complejidad espacial

La memoria adicional que usa el algoritmo. Una lista auxiliar de tamaño

n

O(n)

; una matriz

n\times n

O(n^2)

. La recursión también ocupa memoria: cada llamada pendiente está en la pila, así que una recursión de profundidad

n

usa

O(n)

Qué tamaños son abordables

En un ordenador se hacen del orden de

10^8

–

10^9

operaciones sencillas por segundo:

Complejidad	$n$ máximo en ~1 segundo
$O(\log n)$ , $O(1)$	Cualquiera
$O(n)$	~ $10^8$
$O(n\log n)$	~ $10^7$
$O(n^2)$	~ $10^4$
$O(n^3)$	~500
$O(2^n)$	~27
$O(n!)$	~11

Ejemplos resueltos

Ejemplo 1 · Dos bucles seguidos

def f(a):
    total = 0
    for x in a:            # n vueltas
        total += x
    for x in a:            # n vueltas
        for y in a:        # n vueltas cada una
            total += x * y
    return total

O(n) + O(n^2) = O(n^2)

Ejemplo 2 · Un 'in' dentro de un bucle

def duplicados(a):
    vistos = []
    for x in a:
        if x in vistos:     # O(n) en una lista
            return True
        vistos.append(x)
    return False

O(n^2)

. Cambiando vistos = [] por vistos = set(), el in pasa a

O(1)

y el total a

O(n)

: un cambio de una línea divide el tiempo por miles con muchos datos.

Ejemplo 3 · Bucle logarítmico

def bits(n):
    c = 0
    while n > 0:
        n //= 2
        c += 1
    return c

O(\log n)

: cuenta las cifras binarias de

n

Ejemplo 4 · Bucle dependiente

for i in range(n):
    for j in range(i, n):
        hacer_algo()       # O(1)

Vueltas:

n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}

O(n^2)

, aunque haga la mitad de trabajo que dos bucles completos.

Ejemplo 5 · Recursión con una rebanada

def suma(a):
    if not a:
        return 0
    return a[0] + suma(a[1:])

Parece

O(n)

, pero a[1:] copia la lista:

T(n) = T(n-1) + O(n)

, que da

O(n^2)

en tiempo y

O(n^2)

en memoria total copiada. Pasando un índice en lugar de rebanar, baja a

O(n)

Ejemplo 6 · ¿Cuánto tardará?

Un algoritmo

O(n^2)

tarda 1 s con

n = 10\,000

. Con

n = 100\,000

10^2 = 100

veces más, unos 100 s. Uno

O(n\log n)

que tarde 1 s con

10^4

datos tardaría unos 12,5 s con

10^5

Errores frecuentes

Contar las líneas en vez de las vueltas. Un in, un sort o una rebanada en una línea pueden ser $O(n)$ o más.
Multiplicar bucles que van uno detrás de otro. Se suman; solo se multiplican si están anidados.
Decir que un bucle de 1000 vueltas fijas es $O(n)$ . Si no depende de la entrada, es $O(1)$ .
Olvidar la memoria de la pila en la recursión.
Confundir el mejor caso con el coste del algoritmo. Se suele dar el peor caso.

Preguntas frecuentes

¿Importan las constantes?

En la notación O no, pero en la práctica sí: un algoritmo

O(n)

con una constante enorme puede ser más lento que uno

O(n\log n)

para los tamaños reales. Por eso, para datos pequeños, inserción le gana a merge sort, y las bibliotecas combinan los dos. Lo definitivo es medir.

¿Cómo se mide el tiempo real de un programa?

En Python, con el módulo timeit o con time.perf_counter() antes y después. Conviene probar con varios tamaños y ver cómo crece: si al duplicar

n

el tiempo se cuadruplica, es cuadrático. El simulador de mejor y peor caso muestra esta idea.

Temas relacionados

Notación asintótica

O, Ω y Θ, y recurrencias.

Mejor y peor caso

Cuándo un algoritmo tarda más.

Búsqueda binaria

El ejemplo clásico de O(log n).

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Cómo calcular la complejidad de un algoritmo: bucles, recursión y ejemplos de código

Lo que vas a aprender

Fundamentos teóricos

Operaciones elementales

Reglas básicas

Bucles típicos

Recursión

El coste oculto de las estructuras de datos

Complejidad espacial

Qué tamaños son abordables

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Notación asintótica

Mejor y peor caso

Búsqueda binaria

​Lo que vas a aprender

​Fundamentos teóricos

​Operaciones elementales

​Reglas básicas

​Bucles típicos

​Recursión

​El coste oculto de las estructuras de datos

​Complejidad espacial

​Qué tamaños son abordables

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Notación asintótica

Mejor y peor caso

Búsqueda binaria

Lo que vas a aprender

Fundamentos teóricos

Operaciones elementales

Reglas básicas

Bucles típicos

Recursión

El coste oculto de las estructuras de datos

Complejidad espacial

Qué tamaños son abordables

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados