Dominando Big‑O Complexity: Guía práctica

23 de mayo de 2024

¿Alguna vez te has preguntado por qué tu aplicación React se vuelve lenta cuando crece el tráfico o los datos? La respuesta suele condensarse en dos palabras: Big‑O.

Big‑O describe cómo crece el coste (tiempo o memoria) de un algoritmo cuando el tamaño de los datos, n, tiende a infinito. Es una cota superior asintótica: nos indica el peor crecimiento posible. Para un análisis completo existen también Ω (mejor caso) y Θ (caso promedio).

Aunque nació en círculos académicos, dominar Big‑O marca la diferencia entre una app que vuela y otra que frustra a tus usuarios.

Leyenda de colores

Color	Complejidad	Velocidad aproximada
🟢	O(1)	Constante (instantánea)
🔵	O(log n)	Logarítmica
🟣	O(n)	Lineal
🟡	O(n log n)	Sub-cuadrática (ordenamiento)
🟠	O(n²)	Cuadrática
🔴	O(2ⁿ)	Exponencial

#1 — 🟢 O(1) – El Flash de los algoritmos

1// Acceder a una propiedad – coste constante respecto a n
2const user = { id: 1, name: 'Ana', email: 'ana@dev.com' }
3const userName = user.name // ⚡ Instantáneo
4
5// Leer por índice en un array
6const firstItem = items[0]
7
8// React: desencadenar una actualización de estado
9// La llamada es O(1), pero el render posterior depende del tamaño del árbol.
10const [count, setCount] = useState(0)
11setCount(count + 1)

En la vida real: mostrar el nombre del usuario logueado, flags de autorización, leer el primer elemento de una lista.

#2 — 🟣 O(n) – El currante constante

1// Recorrer todos los productos y pintarlos
2function ProductList({ products }: { products: Product[] }) {
3  return (
4    <div className="grid grid-cols-3 gap-4">
5      {products.map((product) => (
6        <ProductCard key={product.id} product={product} />
7      ))}
8    </div>
9  )
10}
11
12// Buscar un usuario en un array no ordenado
13const findUserByEmail = (users: User[], email: string) =>
14  users.find((u) => u.email === email) // ⇢ en el peor caso revisa todos

En la vida real: renderizar listas, validar formularios, filtrar tablas.

#3 — 🔵 O(log n) – El detective inteligente

1// Búsqueda binaria – recuerda: el array DEBE venir ordenado
2function binarySearch<T extends { id: number }>(
3  list: T[],
4  target: number,
5): T | null {
6  let left = 0
7  let right = list.length - 1
8
9  while (left <= right) {
10    const mid = Math.floor((left + right) / 2)
11
12    if (list[mid].id === target) return list[mid]
13    list[mid].id < target ? (left = mid + 1) : (right = mid - 1)
14  }
15
16  return null
17}

En la vida real: autocompletados, saltos de paginación, navegación jerárquica.

#4 — 🟡 O(n log n) – El gran organizador

La mayoría de algoritmos de ordenamiento eficientes (quicksort, mergesort, timsort –el que usa Array.sort en V8) viven aquí.

1const sorted = products.slice().sort((a, b) => a.price - b.price) // O(n log n)

En la vida real: tablas ordenables, drag‑and‑drop con reordenamiento, algoritmos de búsqueda que combinan sort + binary search.

#5 — 🟠 O(n²) – El villano de la performance

1// ❌ Comparar cada par de usuarios – doble bucle
2function findDuplicateEmails(users: User[]) {
3  const duplicates: User[] = []
4
5  for (let i = 0; i < users.length; i++) {
6    for (let j = i + 1; j < users.length; j++) {
7      if (users[i].email === users[j].email) {
8        duplicates.push(users[i])
9      }
10    }
11  }
12
13  return duplicates
14}
15
16// ✅ Versión O(n) usando Map
17function findDuplicateEmailsOptimized(users: User[]) {
18  const map = new Map<string, User[]>()
19  const duplicates: User[] = []
20
21  users.forEach((u) => {
22    if (map.has(u.email)) {
23      map.get(u.email)!.push(u)
24    } else {
25      map.set(u.email, [u])
26    }
27  })
28
29  map.forEach((arr) => {
30    if (arr.length > 1) {
31      duplicates.push(...arr)
32    }
33  })
34
35  return duplicates
36}

Cuándo aparece: comparaciones todos‑contra‑todos, validaciones mal planteadas, Array.sort con un comparator costoso.

#6 — 🔴 O(2ⁿ) – El monstruo exponencial

1// Fibonacci recursivo – crece como 2ⁿ
2function fibExp(n: number): number {
3  if (n <= 1) return n
4  return fibExp(n - 1) + fibExp(n - 2)
5}
6
7// ✅ Memoización – convierte el coste en O(n)
8const fibMemo = (() => {
9  const cache = new Map<number, number>()
10
11  return function fib(n: number): number {
12    if (cache.has(n)) return cache.get(n)!
13
14    const res = n <= 1 ? n : fib(n - 1) + fib(n - 2)
15    cache.set(n, res)
16
17    return res
18  }
19})()
20
21// ✅ Iterativo – igualmente O(n) y sin recursión profunda
22function fibIter(n: number) {
23  let a = 0,
24    b = 1
25
26  for (let i = 0; i < n; i++) {
27    ;[a, b] = [b, a + b]
28  }
29
30  return a
31}

Complejidad espacial

Optimizar tiempo a veces dispara memoria (y viceversa). La memoización de fibMemo usa O(n) espacio para ganar tiempo. Siempre evalúa si la RAM disponible justifica el ahorro de CPU.

Ejemplos de la vida real en React/Next.js

1. El filtro de búsqueda que mata tu app

1// ❌ Se recalcula en cada pulsación – O(n) por letra
2function ProductSearch({ products }: { products: Product[] }) {
3  const [query, setQuery] = useState('')
4
5  const filtered = products.filter((p) =>
6    p.name.toLowerCase().includes(query.toLowerCase()),
7  ) // n dependiente del tamaño de la lista
8
9  return (
10    <>
11      <input placeholder="Buscar…" onChange={(e) => setQuery(e.target.value)} />
12      {filtered.map((p) => (
13        <ProductCard key={p.id} product={p} />
14      ))}
15    </>
16  )
17}
18
19// ✅ Debounce + useMemo
20function ProductSearchOptimized({ products }: { products: Product[] }) {
21  const [query, setQuery] = useState('')
22  const [debounced, setDebounced] = useState('')
23
24  // 1) Debounce – evita recalcular en cada tecla
25  useEffect(() => {
26    const t = setTimeout(() => setDebounced(query), 300)
27    return () => clearTimeout(t)
28  }, [query])
29
30  // 2) Memo – solo ejecuta el filtro cuando cambian datos relevantes
31  const filtered = useMemo(() => {
32    if (!debounced) return products
33
34    const q = debounced.toLowerCase()
35    return products.filter((p) => p.name.toLowerCase().includes(q))
36  }, [products, debounced])
37
38  return (
39    <>
40      <input placeholder="Buscar…" onChange={(e) => setQuery(e.target.value)} />
41      {filtered.map((p) => (
42        <ProductCard key={p.id} product={p} />
43      ))}
44    </>
45  )
46}

Nota: useMemo evita el cálculo caro, no el render. Si el árbol es grande, combina esta técnica con virtualización (react-window, @tanstack/react-virtual).

2. API Routes y el problema N+1

1// ❌ O(n²) – consulta N+1
2export async function GET() {
3  const users = await db.user.findMany()
4  const enriched = []
5
6  for (const u of users) {
7    const orders = await db.order.findMany({ where: { userId: u.id } })
8    enriched.push({ ...u, orderCount: orders.length })
9  }
10
11  return Response.json(enriched)
12}
13
14// ✅ O(n) – join en una sola query + select para reducir payload
15export async function GET() {
16  const users = await db.user.findMany({
17    select: {
18      id: true,
19      name: true,
20      orders: { select: { id: true } },
21    },
22  })
23
24  return Response.json(
25    users.map((u) => ({
26      ...u,
27      orderCount: u.orders.length,
28    })),
29  )
30}

3. Paginación vs. cargar todo

1// ❌ Cargar 10 000 productos de golpe – RIP memoria y TTFB
2function Catalog() {
3  const [products, setProducts] = useState<Product[]>([])
4
5  useEffect(() => {
6    fetch('/api/products')
7      .then((r) => r.json())
8      .then(setProducts)
9  }, [])
10
11  return (
12    <div className="grid grid-cols-4 gap-4">
13      {products.map((p) => (
14        <ProductCard key={p.id} product={p} />
15      ))}
16    </div>
17  )
18}
19
20// ✅ Paginación infinita + cleanup de observers
21function InfiniteCatalog() {
22  const [page, setPage] = useState(1)
23  const { data, isFetchingNextPage, fetchNextPage } = useInfiniteQuery(
24    ['products'],
25    ({ pageParam = 1 }) =>
26      fetch(`/api/products?page=${pageParam}&limit=20`).then((r) => r.json()),
27    { getNextPageParam: (_, pages) => pages.length + 1 },
28  )
29
30  const loader = useRef<HTMLDivElement>(null)
31
32  useEffect(() => {
33    const io = new IntersectionObserver((entries) => {
34      if (entries[0].isIntersecting && !isFetchingNextPage) {
35        fetchNextPage()
36      }
37    })
38
39    if (loader.current) {
40      io.observe(loader.current)
41    }
42
43    return () => io.disconnect() // 🧹 evita fugas
44  }, [fetchNextPage, isFetchingNextPage])
45
46  return (
47    <>
48      <div className="grid grid-cols-4 gap-4">
49        {data?.pages
50          .flat()
51          .map((p: Product) => <ProductCard key={p.id} product={p} />)}
52      </div>
53      <div ref={loader} className="h-8" />
54    </>
55  )
56}

Cache ≈ O(1): React Query | SWR

Los data‑fetching libraries añaden memoización automática: la primera petición puede ser O(n), pero las lecturas sucesivas desde caché son O(1).

1const { data } = useQuery(['product', id], () =>
2  fetch(`/api/product/${id}`).then((r) => r.json()),
3)

Herramientas para medir y optimizar

React DevTools Profiler

Disponible solo en development; mide la duración de renders:

1<Profiler
2  id="ProductList"
3  onRender={(id, phase, dur) => {
4    console.log(`${id} (${phase}) tardó ${dur.toFixed(2)} ms`)
5  }}
6>
7  <ProductList products={products} />
8</Profiler>

Performance API (mark/measure)

1performance.mark('start')
2expensiveTask()
3performance.mark('end')
4performance.measure('expensiveTask', 'start', 'end')
5console.table(performance.getEntriesByName('expensiveTask'))

Web Vitals

Core Web Vitals (INP, LCP, CLS...) ligan tus algoritmos con la experiencia real del usuario. Mide con Lighthouse o el paquete web-vitals.

Regla de oro

Mide antes de optimizar. Muchas veces el cuello de botella está donde menos lo esperas.

Un micro‑benchmark sencillo:

1async function benchmark(name: string, fn: () => void, iterations = 50) {
2  const times = [] as number[]
3
4  for (let i = 0; i < iterations; i++) {
5    const t0 = performance.now()
6    await fn()
7    times.push(performance.now() - t0)
8  }
9
10  const avg = times.reduce((a, b) => a + b, 0) / times.length
11  console.log(`${name}: ${avg.toFixed(2)} ms`)
12}

Comentarios finales

Big‑O no es paja teórica: es tu superpoder para escalar. Un código que funciona con 10 elementos debe funcionar con 10 000. Si no, es hora de medir, analizar y optimizar.

¡Ahora ve y mejora el mundo una función O(n) a la vez! 🚀✨