Big-O en C - 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
int contar_pares(const int *v, int n) {
  int pares = 0, impares = 0;
  for (int i = 0; i < n; i++) if (v[i] % 2 == 0) pares++;
  for (int i = 0; i < n; i++) if (v[i] % 2 != 0) impares++;
  return pares + impares;
}

// Mejor: un solo loop O(n)
int contar_pares_una_pasada(const int *v, int n) {
  int pares = 0, impares = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] % 2 == 0) pares++;
    else impares++;
  }
  return pares + impares;
}

9.3 Usar break cuando corresponde

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

int contiene(const int *v, int n, int objetivo) {
  for (int i = 0; i < n; i++) {
    if (v[i] == objetivo) {
      // mejor caso O(1) si está al inicio
      return 1;
    }
  }
  return 0; // peor caso O(n)
}

9.4 Precomputación

Guardar resultados intermedios evita recomputar valores caros.

// Prefijo de sumas para responder rangos en O(1)
void prefijos(const int *v, int n, int *p) {
  p[0] = 0;
  for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
}

int suma_rango(const int *p, int l, int r) { // r exclusivo
  return p[r] - p[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
int fib(int n, int *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.

void intercambiar(int *a, int *b) {
  if (a == b) return; // evita swap trivial
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

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
int contar_pares_cuadratico(const int *v, int n) {
  int pares = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (v[i] == v[j]) pares++;
    }
  }
  return pares;
}

// O(n log n): ordenar y agrupar
int comparar_ints(const void *a, const void *b) {
  int ia = *(const int*)a, ib = *(const int*)b;
  return (ia > ib) - (ia < ib);
}

int contar_pares_ordenando(int *v, int n) {
  qsort(v, n, sizeof(int), comparar_ints); // O(n log n)
  int pares = 0;
  for (int i = 0; i < n; ) {
    int j = i + 1;
    while (j < n && v[j] == v[i]) j++;
    int 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.

Retornar

9 - Cómo optimizar un algoritmo