Mejor, Peor y Promedio
Tres Maneras de Medir un Algoritmo
El costo de cualquier algoritmo depende de su entrada. Dos entradas del mismo tamaño pueden producir tiempos de ejecución salvajemente 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 la búsqueda lineal sobre una lista de N elementos: Ω(1) — el objetivo ocupa la primera posición. Una comparación, hecho.
Peor caso — O (O grande): la entrada que hace que el algoritmo termine más lentamente. Para la búsqueda lineal: O(N) — el objetivo está en la última posición en la lista, o no aparece en absoluto. Cada elemento requiere inspección.
Promedio caso — Θ (Theta): costo esperado sobre todos los posibles inputs, suponiendo una distribución uniforme. Para la búsqueda lineal con el objetivo igualmente probable de ocupar cualquier una de las N posiciones: Θ(N/2) = Θ(N). El coeficiente constante 1/2 se elimina porque Theta expresa el crecimiento asintótico estrecho, no los coeficientes exactos.
¿Por qué el Peor Caso Predomina
Los sistemas deben manejar el peor caso. Una consulta de base de datos que promedia 10 ms pero ocasionalmente toma 60 segundos produce un fallo visible para el usuario. Los ingenieros diseñan para los límites de peor caso para que el rendimiento se mantenga predecible sin importar la entrada. El análisis de caso promedio tiene valor en configuraciones probabilísticas, pero el análisis de caso peor proporciona garantías.
Análisis de Caso de Búsqueda Binaria
La búsqueda binaria solo funciona en arrays ordenados. En cada paso: compare el objetivo con el elemento en el punto medio. Si el objetivo es igual al punto medio, devuélvalo. Si el objetivo es más pequeño, siga recursivamente a la izquierda. Si es más grande, siga recursivamente a la derecha.
Cada comparación elimina la mitad de los candidatos restantes.
Crecimiento de Memoria y Comercio Tiempo-Espacio
Contar Memoria, No Operaciones
La complejidad de tiempo mide el número de operaciones que ejecuta un algoritmo. La complejidad de espacio mide la memoria adicional que asigna más allá de su entrada. Ambos importan en los sistemas de producción: un algoritmo rápido que asigna O(N²) memoria agotará un servidor.
O(1) espacio: memoria constante adicional independientemente de N. Un ordenamiento in-situ (por ejemplo, ordenamiento de inserción) intercambia elementos dentro del array original. Usa unas pocas variables temporales - O(1) sin importar cuán grande sea el array.
O(N) espacio: memoria proporcional al tamaño de la entrada. Crear una copia de un array de N elementos requiere N espacios. Construyendo un conjunto de hash a partir de una lista de N cadenas almacena hasta N entradas.
O(N²) espacio: memoria proporcional a N². Construyendo una matriz de vecindad N×N para un grafo con N vértices requiere N² celdas. A N = 10,000 vértices, eso es 10^8 entradas - cientos de megabytes para una simple cuadrícula booleana.
Comercio Tiempo-Espacio
Uno de los movimientos fundamentales en el diseño de algoritmos: comerciar espacio por tiempo, o tiempo por espacio.
Las tablas de hash usan O(N) espacio adicional para lograr O(1) búsqueda. Sin la tabla de hash, un escaneo sobre una lista logra O(N) búsqueda con O(1) espacio adicional. La tabla de hash paga memoria para comprar velocidad.
La memorización almacena resultados previamente computados (O(N) o más espacio) para evitar recomputarlos. Fibonacci recursivo sin memorización corre en O(2^N) tiempo. Con memorización: O(N) tiempo y O(N) espacio. La inversión de espacio reduce el tiempo exponencial.
Diccionario de Hash vs Lista Ordenada
Comparar dos estrategias para contar las ocurrencias de palabras en un documento de N palabras:
Estrategia A: un diccionario (mapa de hash). Insertar cada palabra; incrementar su conteo.
Estrategia B: mantener una lista ordenada de palabras vistas; usar búsqueda binaria para verificar el membresía antes de insertar.
Análisis Amortizado: Esparcir el Costo
Cuando un Gasto Ocasiona no Ruina el Desempeño Promedio
Algunas operaciones son ocasionalmente caras pero baratas en promedio a lo largo de una secuencia. El análisis amortizado calcula el costo promedio por operación en toda la secuencia - no el costo peor caso de una operación individual.
Array dinámico (lista de Python, ArrayList de Java): comienza con una capacidad de 1. Cuando está lleno, se duplica la capacidad. El doblar copia todos los elementos existentes: O(N) trabajo para una anexión. Pero las duplicaciones son raras. Después de N inserciones totales, ¿cuántas operaciones de copia ocurrieron en total?
Las duplicaciones ocurren en tamaños 1, 2, 4, 8, ..., N/2. Contagem de copias: 1 + 2 + 4 + ... + N/2. Este es un sumatorio de una serie geométrica con un total de copias de N − 1 a través de todos los N anexiones. Costo promedio de copias por inserción: (N − 1) / N < 1, por lo que O(1) amortizado por inserción a pesar de O(N) costo peor caso por duplicación.
¿Por qué el Análisis Amortizado Importa
Un sistema que ocasionalmente se detiene para redimensionarse, reequilibrarse o compactar una estructura puede parecer tener operaciones individuales de alarmante costo peor caso. El análisis amortizado revela que la alarma es falsa: los eventos caros ocasionales se pagan con las muchas baratas. Comprender el costo amortizado evita sobreingeniería: agregar complejidad para evitar una rara O(N) operación que contribuye solo O(1) amortizado es trabajo desperdiciado.
Más profundo: El curso no hamming aplica el análisis de complejidad a defectos en el software en producción. Vea [Capítulo perdido: Complejidad algorítmica](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: Defecto sedimentario](/en/un/unhamming_moad_sedimentary).
Insertar en Hash Table Amortizado
Una tabla de hash comienza vacía y duplica su capacidad cuando el factor de carga supera 0.75. Insertar 1,000 elementos desencadena exactamente 10 duplicaciones de capacidad en 1, 2, 4, 8, 16, 32, 64, 128, 256 y 512.