6 - Análisis asintótico paso a paso

Una buena estimación de Big-O comienza identificando qué partes del código crecen con el tamaño de la entrada. En este tema seguimos un flujo práctico para algoritmos en C y repasamos ejemplos clásicos.

6.1 Cómo analizar un algoritmo en C

  • Define la entrada: qué significa n (tamaño del array, nodos, longitud de cadena).
  • Ubica operaciones dominantes: asignaciones, comparaciones, accesos a memoria repetidos.
  • Identifica ciclos y recursión: contar cuántas veces se ejecuta cada bloque.
  • Simplifica términos: conserva el factor de crecimiento que domina al aumentar n.
  • Comprueba con casos límite: n = 0, n = 1, y valores grandes para validar la intuición.

6.2 Contar operaciones dominantes

int suma(const int *v, int n) {
  int total = 0;                 // 1 operación
  for (int i = 0; i < n; i++) {  // se repite n veces
    total += v[i];               // 1 suma + 1 acceso por iteración
  }
  return total;                  // 1 operación
}

La cantidad total de operaciones es proporcional a n; al descartar constantes queda O(n). El objetivo no es contar cada instrucción en ensamblador, sino encontrar la expresión que crece con n.

6.3 Loops anidados

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // bloque O(1)
  }
}

El bloque interno se ejecuta n veces por cada vuelta externa: n * n = n^2 operaciones dominantes. Si el límite interno depende de i (por ejemplo, j <= i), el conteo es n(n+1)/2, que sigue siendo O(n^2) por la simplificación asintótica.

6.4 Recorridos de arrays

Recorrer un array completo implica O(n), pero truncar el recorrido puede cambiar el escenario:

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

Si el array está ordenado y se usa búsqueda binaria, el mismo problema pasa a O(log n). Registrar cuándo el ciclo puede cortar antes ayuda a distinguir mejor, promedio y peor caso.

6.5 Recursión: ecuaciones de recurrencia

Un algoritmo recursivo se modela como una ecuación que relaciona T(n) con subproblemas más chicos:

  • T(n) = T(n-1) + O(1) → recorridos lineales (ej. imprimir lista enlazada). Solución: O(n).
  • T(n) = 2T(n/2) + O(n) → divide y vencerás con combinación lineal (ej. mergesort). Solución: O(n log n).
  • Aplicar el teorema maestro o expandir manualmente la recurrencia permite simplificar el orden.

6.6 Ejemplos prácticos

Suma de elementos (lineal):

int suma_elementos(const int *v, int n) {
  int total = 0;
  for (int i = 0; i < n; i++) total += v[i];
  return total; // O(n)
}

Bubble sort simplificado (cuadrático):

void bubble_sort(int *v, int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
        int aux = v[j];
        v[j] = v[j + 1];
        v[j + 1] = aux;
      }
    }
  }
  // Dos loops anidados => O(n^2)
}

Si el array ya está ordenado podrías cortar temprano al detectar que no hubo intercambios, reduciendo el mejor caso a O(n).

Quicksort (visión previa):

int particion(int *v, int inicio, int fin) {
  int pivote = v[fin];
  int i = inicio - 1;
  for (int j = inicio; j < fin; j++) {
    if (v[j] <= pivote) {
      i++;
      int aux = v[i];
      v[i] = v[j];
      v[j] = aux;
    }
  }
  int aux = v[i + 1];
  v[i + 1] = v[fin];
  v[fin] = aux;
  return i + 1;
}

void quicksort(int *v, int inicio, int fin) {
  if (inicio >= fin) return;
  int p = particion(v, inicio, fin);
  quicksort(v, inicio, p - 1);
  quicksort(v, p + 1, fin);
}

El tiempo esperado es O(n log n) si el pivote divide razonablemente. El peor caso (O(n^2)) ocurre si el pivote deja particiones muy desbalanceadas, algo que se mitiga eligiendo un pivote aleatorio o la mediana de tres.

Retornar