5 - Casos mejor, promedio y peor

Un mismo algoritmo puede tener costos distintos según la distribución de datos. Aquí diferenciamos mejor, promedio y peor caso, y mostramos cómo medirlos en C.

5.1 ¿Por qué no existe un solo Big-O?

Big-O suele referirse al peor caso, pero otros escenarios importan:

• Mejor caso: entrada favorable que minimiza pasos.
• Promedio: entrada típica bajo una distribución asumida.
• Peor caso: entrada que maximiza el trabajo; clave para garantizar límites.

Elegir cuál reportar depende del riesgo aceptable y del tipo de datos con el que trabajará el algoritmo.

5.2 Ejemplos

Búsqueda lineal (array desordenado):

• Mejor: O(1) si el elemento está en la primera posición.
• Promedio: O(n) porque en promedio se revisa la mitad, pero Big-O no simplifica más.
• Peor: O(n) si no se encuentra o está al final.

Búsqueda binaria (array ordenado):

• Mejor: O(1) si justo está en el medio.
• Promedio y peor: O(log n) por dividir en cada paso.

Inserción en listas enlazadas:

• Al inicio con puntero a la cabeza: O(1) en todos los casos.
• Al final sin puntero a cola: mejor O(1) si está vacía, peor O(n) si hay que recorrer.

Búsqueda en BST:

• Mejor/promedio en un árbol balanceado: O(log n).
• Peor en un árbol degenerado (como lista): O(n).

5.3 Graficar crecimiento

Graficar curvas (por ejemplo con CSV y una hoja de cálculo) ayuda a visualizar cómo se separan los escenarios: una línea O(n) crece más lento que O(n^2) y se nota al duplicar n. Para casos mejor/promedio/peor, se suelen mostrar tres curvas o bandas.

5.4 Implementación en C para medir tiempos reales

Un esquema simple usando clock() permite medir cada caso. Para búsqueda lineal:

#include <stdio.h>
#include <time.h>

int busqueda_lineal(const int *v, int n, int objetivo) {
  for (int i = 0; i < n; i++) {
    if (v[i] == objetivo) return i;
  }
  return -1;
}

double medir_busqueda(const int *v, int n, int objetivo) {
  clock_t inicio = clock();
  busqueda_lineal(v, n, objetivo);
  clock_t fin = clock();
  return (double)(fin - inicio) / CLOCKS_PER_SEC;
}

int main(void) {
  int datos[100000];
  for (int i = 0; i < 100000; i++) datos[i] = i;
  printf("Peor caso: %.6f s\n", medir_busqueda(datos, 100000, -1));
  printf("Mejor caso: %.6f s\n", medir_busqueda(datos, 100000, datos[0]));
  return 0;
}

Repite mediciones y promedia para reducir ruido; fija afinidad de CPU o cierra procesos para obtener resultados consistentes.

5.5 Diferencias en práctica vs teoría

• La complejidad asintótica describe tendencias; constantes y caché pueden cambiar el cruce de curvas en tamaños pequeños.
• Optimizaciones del compilador (inlining, vectorización) alteran el tiempo real sin cambiar el Big-O.
• El peor caso teórico puede ser improbable; si los datos están parcialmente ordenados, el rendimiento real mejora.
• Medir en múltiples tamaños y escenarios es la forma más fiable de contrastar teoría con práctica.