🧠 Complejidad + modelo de memoria

Por qué importa

La velocidad y el espacio son lo que separa una solución aceptada de una que da TLE (límite de tiempo excedido).

La idea

Piensa en operaciones por tamaño de la entrada. list.append() es O(1) amortizado; list.insert(0, x) es O(n) porque todo se desplaza. La búsqueda en set / dict es O(1); la pertenencia en una list (x in lst) es O(n).

Mira O(n²) en acción

El ordenamiento de burbuja compara cada par adyacente y burbujea el mayor hacia el final en cada pasada. Toca Auto y cuenta: 24 elementos requieren ~200 comparaciones. Duplicar a 48 no tomaría 2×, tomaría ~4×. Así se ve O(n²).

Pruébalo

Cronometra la diferencia entre la pertenencia en una list y en un set:

import time

N = 50000
data = list(range(N))
data_set = set(data)
needles = [N - 1, N // 2, 0]

t0 = time.perf_counter()
hits_list = sum(1 for x in needles if x in data)
t1 = time.perf_counter()
hits_set = sum(1 for x in needles if x in data_set)
t2 = time.perf_counter()

print(f"list lookups: {hits_list}  time: {(t1-t0)*1e6:.1f} µs")
print(f"set  lookups: {hits_set}  time: {(t2-t1)*1e6:.1f} µs")

Copia superficial frente a profunda: los mutables sorprenden a la gente:

import copy

grid = [[0] * 3 for _ in range(3)]
shallow = list(grid)       # same inner lists!
deep = copy.deepcopy(grid)

shallow[0][0] = 99
deep[0][0] = -1

print("grid    :", grid)
print("shallow :", shallow)
print("deep    :", deep)

Mutación en el sitio frente a objeto nuevo:

# sorted() makes a new list, sort() mutates in place
nums = [3, 1, 4, 1, 5]
asc = sorted(nums)         # new
nums.sort(reverse=True)    # in place
print("asc :", asc)
print("nums:", nums)

Verificación rápida

• P: ¿Qué es más rápido para la pertenencia: una lista o un conjunto? R: El conjunto.

Mini ejercicios

• Identifica qué tipos son mutables.
• Explica por qué b = a puede ser peligroso.

Errores comunes

• Error: Suponer que b = a copia los datos. Solución: Usa a.copy() o list(a).
• Error: Mutar una entrada dentro de una función sin querer. Solución: Documéntalo, o copia primero.

Conclusiones clave

• list.append() es O(1) amortizado; list.insert(0, x) es O(n).
• x in set / x in dict es O(1); x in list es O(n).
• list(other) es una copia SUPERFICIAL: los mutables interiores se siguen compartiendo.
• copy.deepcopy es correcto pero lento; úsalo solo cuando necesites aislamiento total.