> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Cómo calcular la complejidad de un algoritmo: bucles, recursión y ejemplos de código > Guía práctica para calcular la complejidad temporal y espacial de un programa: operaciones elementales, bucles simples, anidados y dependientes, bucles logarítmicos, llamadas a funciones, recursión, coste de las operaciones de listas, diccionarios y conjuntos, y ejemplos de código analizados línea a línea. La [notación asintótica](https://apuntes.simulab.es/programacion/algoritmos/notacion-asintotica.md) 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](https://apuntes.simulab.es/programacion/c/divide-y-venceras.md)). ### 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$ es $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 > [accordion] Ejemplo 1 · Dos bucles seguidos > > ```python theme={null} > 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)$. > [accordion] Ejemplo 2 · Un 'in' dentro de un bucle > > ```python theme={null} > 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. > [accordion] Ejemplo 3 · Bucle logarítmico > > ```python theme={null} > def bits(n): > c = 0 > while n > 0: > n //= 2 > c += 1 > return c > ``` > > $O(\log n)$: cuenta las cifras binarias de $n$. > [accordion] Ejemplo 4 · Bucle dependiente > > ```python theme={null} > 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. > [accordion] Ejemplo 5 · Recursión con una rebanada > > ```python theme={null} > 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)$. > [accordion] 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 > [accordion] ¿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. > [accordion] ¿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](https://apuntes.simulab.es/programacion/c/mejor-peor-caso.md) muestra esta idea. ## Temas relacionados > [card] [Notación asintótica](https://apuntes.simulab.es/programacion/algoritmos/notacion-asintotica.md) > > O, Ω y Θ, y recurrencias. > [card] [Mejor y peor caso](https://apuntes.simulab.es/programacion/c/mejor-peor-caso.md) > > Cuándo un algoritmo tarda más. > [card] [Búsqueda binaria](https://apuntes.simulab.es/programacion/algoritmos/busqueda-binaria.md) > > El ejemplo clásico de O(log n). This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.