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 Python.

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 Python para medir tiempos reales

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

import time

def busqueda_lineal(valores, objetivo):
  for i, valor in enumerate(valores):
    if valor == objetivo:
      return i
  return -1

def medir_busqueda(valores, objetivo):
  inicio = time.perf_counter()
  busqueda_lineal(valores, objetivo)
  fin = time.perf_counter()
  return fin - inicio

datos = list(range(100000))
print("Peor caso: %.6f s" % medir_busqueda(datos, -1))
print("Mejor caso: %.6f s" % medir_busqueda(datos, datos[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.