Mejor, Peor & Caso Promedio
Tres Formas de Medir un Algoritmo
El costo de cada algoritmo depende de su entrada. Dos entradas del mismo tamaño pueden producir tiempos de ejecución muy diferentes. El análisis de complejidad formaliza tres perspectivas sobre esa variación.
Mejor caso — Ω (Omega): la entrada que hace que el algoritmo termine más rápido. Para búsqueda lineal en una lista de N elementos: Ω(1) — el objetivo ocupa la primera posición. Una comparación, listo.
Peor caso — O (Big O): la entrada que hace que el algoritmo termine más lentamente. Para búsqueda lineal: O(N) — el objetivo está al final de la lista o no aparece en absoluto. Cada elemento requiere inspección.
Caso promedio — Θ (Theta): costo esperado en todas las entradas posibles, asumiendo distribución uniforme. Para búsqueda lineal con el objetivo igualmente probable de ocupar cualquiera de las N posiciones: Θ(N/2) = Θ(N). La constante 1/2 se descarta porque Theta expresa crecimiento asintótico ajustado, no coeficientes exactos.
Por Qué el Peor Caso Domina
Los sistemas deben manejar el peor caso. Una consulta de base de datos que promedia 10 ms pero ocasionalmente tarda 60 segundos produce una falla visible para el usuario. Los ingenieros diseñan para límites del peor caso para que el rendimiento sea predecible independientemente de la entrada. El análisis de caso promedio tiene valor en configuraciones probabilísticas, pero el análisis del peor caso ofrece garantías.
Análisis de Casos de Búsqueda Binaria
La búsqueda binaria funciona solo en matrices ordenadas. En cada paso: compara el objetivo con el elemento en el punto medio. Si el objetivo es igual al punto medio, devuélvelo. Si el objetivo es más pequeño, recursa en la mitad izquierda. Si es más grande, recursa en la mitad derecha.
Cada comparación elimina la mitad de los candidatos restantes.
Crecimiento de Memoria & Compensaciones Tiempo-Espacio
Contando Memoria, No Operaciones
La complejidad temporal mide la cantidad de operaciones que ejecuta un algoritmo. La complejidad espacial mide la memoria adicional que asigna más allá de su entrada. Ambas importan en sistemas de producción: un algoritmo rápido que asigna memoria O(N²) agotará un servidor.
Espacio O(1): memoria extra constante independientemente de N. Una ordenación in-place (p. ej. ordenación por inserción) intercambia elementos dentro de la matriz original. Usa un puñado de variables temporales — O(1) sin importar cuán grande sea la matriz.
Espacio O(N): memoria proporcional al tamaño de entrada. Crear una copia de una matriz de N elementos requiere N espacios. Construir un conjunto hash a partir de una lista de N cadenas almacena hasta N entradas.
Espacio O(N²): memoria proporcional a N². Construir una matriz de adyacencia N×N para un grafo con N vértices requiere N² celdas. En N = 10,000 vértices, son 10^8 entradas — cientos de megabytes para una simple cuadrícula booleana.
Compensaciones Tiempo-Espacio
Uno de los movimientos fundamentales en el diseño de algoritmos: intercambiar espacio por tiempo o tiempo por espacio.
Las tablas hash usan espacio O(N) adicional para lograr búsqueda O(1). Sin la tabla hash, un escaneo sobre una lista logra búsqueda O(N) con espacio O(1) adicional. La tabla hash paga memoria para comprar velocidad.
La memoización almacena resultados previamente calculados (espacio O(N) o más) para evitar recalcularlos. Fibonacci recursivo sin memoización se ejecuta en tiempo O(2^N). Con memoización: tiempo O(N) y espacio O(N). La inversión de espacio reduce el tiempo exponencialmente.
Diccionario Hash vs Lista Ordenada
Compara dos estrategias para contar ocurrencias de palabras en un documento de N palabras:
Estrategia A: un diccionario (mapa hash). Inserta cada palabra; incrementa su conteo.
Estrategia B: mantener una lista ordenada de palabras vistas; usar búsqueda binaria para verificar pertenencia antes de insertar.
Análisis Amortizado: Distribuyendo el Costo
Cuando el Gasto Ocasional No Arruina el Rendimiento Promedio
Algunas operaciones son ocasionalmente costosas pero baratas en promedio en una secuencia. El análisis amortizado calcula el costo promedio por operación en toda la secuencia — no el costo del peor caso de una sola operación.
Matriz dinámica (lista de Python, ArrayList de Java): comienza con capacidad 1. Cuando está llena, duplica la capacidad. Duplicar copia todos los elementos existentes: trabajo O(N) para un append. Pero los doblados son raros. Después de N appends totales, ¿cuántas operaciones de copia total ocurrieron?
Los doblados ocurren en tamaños 1, 2, 4, 8, ..., N/2. Conteos de copia: 1 + 2 + 4 + ... + N/2. Esta es una serie geométrica que suma a N − 1 copias totales en todos los N appends. Copias promedio por append: (N − 1) / N < 1, entonces O(1) amortizado por append a pesar del costo del peor caso O(N) por doblado.
Por Qué el Análisis Amortizado Importa
Un sistema que ocasionalmente se pausa para cambiar tamaño, reequilibrar o compactar una estructura puede parecer que tiene operaciones individuales del peor caso alarmantes. El análisis amortizado revela que la alarma es falsa: los eventos ocasionalmente costosos se pagan con los muchos baratos. Entender el costo amortizado previene la sobreingeniería: agregar complejidad para evitar una operación O(N) rara que contribuye solo O(1) amortizado es trabajo desperdiciado.
Profundizando: El curso unhamming aplica análisis de complejidad a defectos del mundo real en software de producción. Ver El Capítulo Faltante: Complejidad Algorítmica & MOAD-0001: El Defecto Sedimentario.
Inserción Amortizada de Tabla Hash
Una tabla hash comienza vacía y duplica la capacidad siempre que el factor de carga excede 0.75. Insertar 1,000 elementos desencadena exactamente 10 doblados en capacidades 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.