Cada Clase de Complejidad Dibuja una Curva
Grafica el Costo Contra el Tamaño de Entrada
Coloca el tamaño de entrada N en el eje x. Coloca el costo (operaciones, tiempo) en el eje y. Cada clase de complejidad produce una curva distinta. Puedes reconocer la tasa de crecimiento de un algoritmo por la forma de su curva de rendimiento.
O(1) — línea horizontal plana. La función f(N) = 1. Sin pendiente. El costo nunca cambia independientemente de N. Búsqueda en tabla hash: ya sea que la tabla contenga 10 o 10.000.000 elementos, una computación hash salta a la cubeta correcta.
O(log N) — curva ascendente suave, pendiente decreciente. En N = 1.000.000: costo ≈ 20 operaciones. La curva sube abruptamente en N pequeño, luego se aplana. Cada duplicación de N añade exactamente una unidad de costo.
O(N) — línea recta diagonal. Pendiente = 1 (en sentido asintótico). El costo crece a la misma tasa que N. Si N se triplica, el costo se triplica.
O(N log N) — diagonal más empinada con ligera curvatura hacia arriba. Está por encima de O(N) pero por debajo de O(N²). El factor logarítmico añade un multiplicador que crece lentamente a la pendiente lineal.
O(N²) — parábola abierta hacia arriba. La pendiente aumenta a medida que N crece. En N = 10: costo = 100. En N = 100: costo = 10.000. En N = 1.000: costo = 1.000.000.
La Brecha Creciente
La razón O(N²) / O(N) = N. La brecha entre la parábola y la diagonal se ensancha a medida que N crece. En N = 10: brecha de 10×. En N = 100: brecha de 100×. En N = 1.000: brecha de 1.000×. En N = 50.000: brecha de 50.000×. La brecha es igual a N — siempre.
Calculando la Brecha de Escala
Un grafo de dependencia grande contiene 50.000 paquetes (N = 50.000). Un algoritmo se ejecuta en tiempo O(N). Un segundo se ejecuta en O(N²). En este N, la razón O(N²)/O(N) = N = 50.000.
Bisectando un Segmento de Línea
Búsqueda Binaria como Bisección Repetida
Un arreglo ordenado de N elementos forma un segmento de línea de longitud N. La búsqueda binaria biseca repetidamente este segmento:
1. Apunta al punto medio del segmento restante.
2. Si objetivo < punto medio: la mitad derecha desaparece. Recurre en la mitad izquierda.
3. Si objetivo > punto medio: la mitad izquierda desaparece. Recurre en la mitad derecha.
4. Si objetivo = punto medio: hecho.
Después de k bisecciones, el segmento restante tiene longitud N / 2^k. La búsqueda termina cuando esa longitud es igual a 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Entonces la búsqueda binaria en N elementos requiere como máximo log₂N comparaciones.
Dividir por la Mitad y Duplicar: Dos Lados de la Misma Curva
Dividir por la mitad y duplicar son inversos geométricos. La curva exponencial 2^k y la curva logarítmica log₂N son reflexiones una de la otra a través de la línea y = x.
Considera el plegado de papel: una hoja comienza con 0,1 mm de espesor. Cada pliegue duplica el espesor. Después de 42 pliegues: 0,1 mm × 2^42 ≈ 439.804 km — más allá de la luna (384.400 km). La búsqueda binaria ejecuta lo inverso: comienza con N elementos, cada paso divide el recuento por la mitad, alcanza 1 elemento en log₂N pasos.
La geometría: la bisección es una operación autosimilar. Cada bisección produce dos mitades que se ven idénticas en estructura al todo. La recursión y los logaritmos comparten esta autosimilitud.
Comparaciones y Duplicaciones
Un arreglo ordenado contiene 1.048.576 elementos. Nota: 1.048.576 = 2^20.
Una Función Hash como un Mapa Geométrico
Función Hash como Función
Una tabla hash asigna una clave a una cubeta usando una función hash:
cubeta = hash(clave) mod tamaño_tabla
Esta es una función en sentido matemático estricto: asigna un dominio (todas las claves posibles) a un rango (índices de cubeta de 0 a tamaño_tabla − 1). La imagen geométrica: las claves ocupan un espacio; las cubetas ocupan otro. La función hash proyecta claves sobre índices de cubeta.
Búsqueda O(1) — salto directo, sin búsqueda. La función hash calcula el índice de cubeta en tiempo constante. Salta directamente a esa cubeta. Sin recorrido, sin bucle de comparación.
Factor de carga. Con factor de carga 0,75, el 75% de las cubetas contienen al menos un elemento. Por encima de ~0,9, aumentan las colisiones: dos claves se asignan a la misma cubeta, formando una cadena de elementos dentro de esa cubeta. La búsqueda en una cadena larga se degrada a O(N) en el peor caso.
Calidad de Distribución como Geometría
Una función hash bien distribuida esparce las claves uniformemente en todas las cubetas. Geométricamente: el rango de la función cubre su codominio uniformemente. Cada cubeta recibe aproximadamente N / tamaño_tabla claves.
Una función hash pobre agrupa las claves en pocas cubetas. Geométricamente: el rango de la función colapsa a un subconjunto del codominio — la mayoría de las claves se asignan a los mismos pocos puntos. Las cubetas restantes se quedan vacías.
Conexión a MOAD-0001
Reemplazar una lista con un conjunto arregla MOAD-0001 porque un conjunto usa una tabla hash internamente. Escaneo de lista O(N) → búsqueda en tabla hash O(1). Geométricamente: el recorrido lineal a lo largo de una secuencia se transforma en una proyección directa a través de una función. La secuencia desaparece; la función la reemplaza.
Analizando un Hash Distribuido Pobremente
Una tabla hash tiene 1.000 cubetas y 900 elementos (factor de carga 0,9). Una función hash pobre envía 500 de esos elementos a la misma cubeta.