9 - Cómo optimizar un algoritmo

Optimizar no es solo micro-ajustar código: consiste en reducir el orden de crecimiento eligiendo estructuras, cortando trabajo innecesario y simplificando la recursión. Estas pautas ayudan a mejorar el Big-O sin perder claridad.

9.1 Reglas generales

• Medir primero: identifica cuellos usando entradas grandes.
• Simplificar: evita trabajo redundante o cálculos repetidos.
• Elegir estructuras que acorten operaciones clave.
• Prefiere claridad con buen Big-O antes que micro-optimizaciones prematuras.

9.2 Evitar loops innecesarios

Un doble loop sin dependencias puede reemplazarse por una sola pasada si combinamos condiciones.

# Ineficiente: dos recorridos
def contar_pares(valores):
  pares = 0
  impares = 0
  for valor in valores:
    if valor % 2 == 0:
      pares += 1
  for valor in valores:
    if valor % 2 != 0:
      impares += 1
  return pares + impares

# Mejor: un solo loop O(n)
def contar_pares_una_pasada(valores):
  pares = 0
  impares = 0
  for valor in valores:
    if valor % 2 == 0:
      pares += 1
    else:
      impares += 1
  return pares + impares

9.3 Usar break cuando corresponde

Salir temprano reduce el peor caso si la condición favorable es frecuente.

def contiene(valores, objetivo):
  for valor in valores:
    if valor == objetivo:
      # mejor caso O(1) si esta al inicio
      return True
  return False  # peor caso O(n)

9.4 Precomputación

Guardar resultados intermedios evita recomputar valores caros.

# Prefijo de sumas para responder rangos en O(1)
def prefijos(valores):
  p = [0]
  for valor in valores:
    p.append(p[-1] + valor)
  return p

def suma_rango(prefijos, l, r):  # r exclusivo
  return prefijos[r] - prefijos[l]

Calcular los prefijos cuesta O(n); luego cada consulta pasa de O(n) a O(1).

9.5 Optimizar recursión

• Evitar recomputar subproblemas: usa memoización cuando hay solapamiento.
• Limitar profundidad: tail recursion puede convertirse a iteración para ahorrar stack.
• Elegir pivotes o subdivisiones balanceadas: reduce el riesgo de caer en O(n^2).

# Fibonacci con memo
def fib(n, memo):
  if n <= 1:
    return n
  if memo[n] != -1:
    return memo[n]
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  return memo[n]

9.6 Elegir la estructura correcta

• Colas de prioridad para obtener mín/máx en O(log n) en lugar de buscar lineal.
• Tablas hash para búsquedas promedio O(1) en vez de listas.
• Árboles balanceados cuando importan orden y rango (O(log n)).

9.7 Minimizar copias y swaps

Copiar buffers grandes o hacer swaps innecesarios multiplica el costo.

def intercambiar(valores, i, j):
  if i == j:
    return  # evita swap trivial
  valores[i], valores[j] = valores[j], valores[i]

En estructuras grandes, trabaja con punteros o índices para evitar duplicar memoria.

9.8 Ejemplo: mejorar un algoritmo O(n^2) → O(n log n)

Problema: contar cuántos pares de elementos iguales hay en un array.

# O(n^2): compara cada par
def contar_pares_cuadratico(valores):
  pares = 0
  for i in range(len(valores)):
    for j in range(i + 1, len(valores)):
      if valores[i] == valores[j]:
        pares += 1
  return pares

# O(n log n): ordenar y agrupar
def contar_pares_ordenando(valores):
  valores.sort()  # O(n log n)
  pares = 0
  i = 0
  while i < len(valores):
    j = i + 1
    while j < len(valores) and valores[j] == valores[i]:
      j += 1
    repeticiones = j - i
    pares += (repeticiones * (repeticiones - 1)) // 2
    i = j
  return pares

Ordenar permite agrupar iguales y contarlos en una sola pasada. El costo dominante pasa a ser el sort (O(n log n)), mejor que el doble loop cuadrático para n grande.