Cada clase de complejidad dibuja una curva
Dibuje el costo contra el tamaño de entrada
Asegure que el tamaño de entrada N esté en el eje x. Asegure que el costo (operaciones, tiempo) esté en el eje y. Cada clase de complejidad produce una curva distinta. Puede 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. Consulta de tabla de hash: ya que la tabla tenga 10 o 10,000,000 elementos, un cálculo de hash salta directamente al recipiente correcto.
O(log N) — curva suave hacia arriba, pendiente disminuyendo. A N = 1,000,000: costo ≈ 20 operaciones. La curva se eleva rápidamente a pequeños N, luego se aplana. Cada duplicación de N agrega exactamente una unidad de costo.
O(N) — línea diagonal recta. Pendiente = 1 (en el 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 inclinada con ligeramente curvatura hacia arriba. Se encuentra por encima de O(N) pero por debajo de O(N²). El factor log añade un multiplicador que crece lentamente al pendiente lineal.
O(N²) — parábola abierta hacia arriba. La pendiente aumenta a medida que N crece. A N = 10: costo = 100. A N = 100: costo = 10,000. A 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 agranda a medida que N crece. A N = 10: 10× brecha. A N = 100: 100× brecha. A N = 1,000: 1,000× brecha. A N = 50,000: 50,000× brecha. La brecha es igual a N — siempre.
Calculando la brecha de escala
Un gran gráfico de dependencias contiene 50,000 paquetes (N = 50,000). Un algoritmo se ejecuta en tiempo O(N). Otro 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 Reiterada
Un array ordenado de N elementos forma un segmento de línea de longitud N. La búsqueda binaria realiza bisecciones repetidas en este segmento:
1. Señalar el punto medio del segmento restante.
2. Si target < punto medio: la mitad derecha desaparece. Recursar en la mitad izquierda.
3. Si target > punto medio: la mitad izquierda desaparece. Recursar en la mitad derecha.
4. Si target = punto medio: terminado.
Después de k bisecciones, el segmento restante tiene una longitud de N / 2^k. La búsqueda termina cuando esa longitud es igual a 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Por lo tanto, la búsqueda binaria en N elementos requiere al menos log₂N comparaciones.
Mitad y Duplicación: Dos Lados del Mismo Curva
La duplicación y la mitad son inversos geométricos. La curva exponencial 2^k y la curva logarítmica log₂N son reflejos uno de otro a lo largo de la línea y = x.
Considere el doblado de papel: una hoja comienza en 0.1 mm de espesor. Cada doblado duplica la grosor. Después de 42 dobleces: 0.1 mm × 2^42 ≈ 439,804 km — más allá de la luna (384,400 km). La búsqueda binaria realiza la operación inversa: comienza en N elementos, cada paso reduce a la mitad el conteo, llega a un elemento en log₂N pasos.
La geometría: la bisectio es una operación auto-similar. Cada bisección produce dos mitades que tienen la misma estructura que el todo. La recursión y los logaritmos comparten esta auto-similitud.
Comparaciones y Duplicaciones
Un array ordenado contiene 1,048,576 elementos. Nota: 1,048,576 = 2^20.
Una Función de Hash como Mapa Geométrico
Función de Hash como Función
Una tabla de hash mapea una clave a un recipiente usando una función de hash:
recipiente = hash(clave) mod tamaño_de_tabla
Esto es una función en el sentido estricto matemático: mapea un dominio (todas las posibles claves) a un rango (índices de recipientes de 0 a tamaño_de_tabla − 1). La imagen geométrica: las claves ocupan un espacio; los recipientes ocupan otro. La función de hash proyecta las claves sobre los índices de recipientes.
O(1) búsqueda - salto directo, sin búsqueda. La función de hash calcula el índice de recipiente en tiempo constante. Salte directamente a ese recipiente. Sin recorrido, sin bucle de comparación.
Factor de carga. Con un factor de carga del 0.75, el 75% de los recipientes contiene al menos un elemento. Por encima de ~0.9, aumentan las colisiones: dos claves se hash en el mismo recipiente, formando una cadena de elementos dentro de ese recipiente. La búsqueda en una cadena larga se degrada a O(N) en el peor de los casos.
Calidad de Distribución como Geometría
Una función de hash bien distribuida esparce las claves de manera uniforme en todos los recipientes. Geométricamente: la función del rango cubre de manera uniforme su codominio. Cada recipiente recibe aproximadamente N / tamaño_de_tabla claves.
Una mala función de hash agrupa claves en unos pocos recipientes. Geométricamente: el rango de la función se derrumba en un subconjunto del codominio - la mayoría de las claves se mapean a los mismos pocos puntos. Los recipientes restantes permanecen vacíos.
Conexión con MOAD-0001
Sustituir una lista por un conjunto resuelve MOAD-0001 porque un conjunto utiliza una tabla de hash internamente. Escaneo O(N) de lista → búsqueda de tabla de hash O(1). Geométricamente: el recorrido lineal a lo largo de una secuencia se transforma en un salto directo a través de una función. La secuencia desaparece; la función la reemplaza.
Analizar una Función de Hash Pobremente Distribuida
Una tabla hash tiene 1,000 recipientes y 900 elementos (factor de carga 0.9). Una mala función de hash envía 500 de esos elementos al mismo recipiente.