Algoritmos base y razonamiento¶

De un vistazo

Materia: Capa 0 · Cimientos · Tiempo de lectura: ~35 min · Requisitos previos: Estructuras de datos y Complejidad algorítmica.

En una frase: no vas a memorizar algoritmos, vas a aprender los patrones de ataque con los que se resuelven la mayoría de los problemas —búsqueda, ordenación, divide y vencerás, recursión, grafos— y, sobre todo, cómo razonar si un algoritmo es correcto y qué cuesta. Cierra la Capa 0.

Por qué esto importa¶

Rara vez implementarás un ordenamiento a mano: tu lenguaje ya trae sort(). Entonces, ¿para qué estudiar algoritmos?

Por dos razones que sí usarás cada semana:

Reconocer el patrón. El 90% de los problemas "nuevos" son un algoritmo clásico disfrazado. Si reconoces "esto es una búsqueda binaria" o "esto es un recorrido de grafo", ya tienes la solución y su coste. Si no, reinventas la rueda, mal y lenta.
Razonar sobre correctez y coste. Saber por qué sort() es O(n log n) y no puede ser mejor, o por qué la búsqueda binaria exige datos ordenados, es lo que te deja elegir bien y depurar cuando algo no cuadra. Es criterio, no recetas.

Preguntas que esto responde:

¿Por qué buscar en Google es instantáneo pero solo si el índice está ordenado?
¿Por qué ningún ordenamiento por comparación puede bajar de O(n log n)?
¿Cómo encuentra un GPS el camino más corto entre millones de calles?
¿Cuándo la recursión es elegante y cuándo es una trampa que peta el stack?

Intuición primero: un algoritmo es una receta con garantías¶

Un algoritmo es una secuencia finita de pasos que resuelve un problema. Pero lo que separa un algoritmo de "unos pasos que parecen funcionar" son dos garantías que hay que saber argumentar:

Correctez: produce el resultado correcto para toda entrada válida, no solo para las que probaste.
Terminación: siempre acaba (no se queda en un bucle infinito).

Y una etiqueta: su coste (la complejidad de la lección anterior). Un buen algoritmo es una receta de la que puedes demostrar que es correcta, que termina, y de la que conoces el precio. Todo lo demás de esta lección son patrones concretos que cumplen esas garantías.

La herramienta mental clave para razonar sobre correctez es el invariante: algo que es verdad antes, durante y después de cada paso. Si encuentras un invariante que garantiza el resultado al terminar, has demostrado que el algoritmo funciona sin probar mil entradas. Lo verás en acción enseguida.

El detalle¶

1. Búsqueda: lineal vs binaria¶

Búsqueda lineal: mira uno a uno hasta encontrarlo. O(n). Funciona siempre, sobre cualquier colección, ordenada o no. Es el suelo: cuando no hay estructura que explotar, no hay más remedio que mirarlo todo.

Búsqueda binaria: si los datos están ordenados, abres por la mitad; si lo que buscas es menor, descartas la mitad derecha; si es mayor, la izquierda; y repites. Cada paso elimina la mitad de lo que queda. O(log n).

graph TB
  A["Buscar 7 en [1,3,5,7,9,11,13]<br/>mitad = 7 ✓ (suerte)"] 
  B["Buscar 3<br/>mitad=7 → 3<7 → mitad izquierda [1,3,5]"]
  C["mitad de [1,3,5] = 3 ✓"]
  B --> C

La potencia del logaritmo es difícil de exagerar: en una lista de mil millones de elementos, la búsqueda lineal puede hacer mil millones de comparaciones; la binaria hace ~30. Pero exige un peaje: los datos tienen que estar ordenados. Esa condición previa es la que explica por qué las bases de datos se rompen la cabeza manteniendo índices ordenados (B-trees): es lo que convierte búsquedas O(n) en O(log n).

El invariante de la búsqueda binaria

"Si el elemento está, está dentro del trozo que aún no he descartado." Es verdad al empezar (el trozo es todo) y sigue siéndolo tras cada paso (solo descartas la mitad donde el elemento no puede estar). Cuando el trozo se queda vacío, el invariante garantiza que no estaba. Eso es una demostración de correctez, sin probar entradas.

2. Ordenación: por qué O(n log n) es el suelo¶

Ordenar es el problema más estudiado de la informática, y no por capricho: ordenar desbloquea la búsqueda binaria, la detección de duplicados, las medianas, los rangos…. Hay dos familias:

Ordenamientos ingenuos (burbuja, inserción, selección): comparan e intercambian con bucles anidados. O(n²). Fáciles de escribir, inservibles a escala. Sirven para entender el problema, no para producción.
Ordenamientos eficientes (merge sort, quicksort, heapsort): O(n log n). Son los que usa tu lenguaje.

El merge sort es el ejemplo perfecto de la técnica estrella de la sección siguiente: parte la lista en dos mitades, ordena cada mitad (recursivamente) y fusiona las dos mitades ordenadas en una pasada. El "parte por la mitad" da el log n; el "fusiona recorriendo" da el n; juntos, O(n log n).

Hay un límite teórico, no es que no seamos listos

Ningún algoritmo que ordene comparando pares de elementos puede bajar de O(n log n) en el peor caso. Se demuestra: hay n! ordenaciones posibles y cada comparación solo distingue entre dos ramas, así que necesitas al menos log(n!) ≈ n log n comparaciones para distinguir la correcta. Es una cota inferior del problema, no una limitación de ingenio. (Solo se baja de ahí si dejas de comparar y explotas la estructura de los datos —como el counting sort con enteros acotados—, pero eso ya no es ordenación por comparación.)

3. Divide y vencerás: partir, resolver, combinar¶

El patrón detrás del merge sort y de la búsqueda binaria es divide y vencerás: si un problema es difícil sobre n datos, pártelo en subproblemas más pequeños del mismo tipo, resuélvelos, y combina las soluciones.

graph TB
  P["Problema (n)"] --> A["subproblema (n/2)"]
  P --> B["subproblema (n/2)"]
  A --> A1["(n/4)"]
  A --> A2["(n/4)"]
  B --> B1["(n/4)"]
  B --> B2["(n/4)"]
  A1 --> C["... hasta casos triviales ..."]

Funciona cuando el problema se descompone en trozos independientes y las soluciones se combinan con un coste razonable. La estructura "partir por la mitad repetidamente" es la que hace aparecer el log n una y otra vez. Reconocer que un problema admite divide y vencerás suele ser el salto de una solución O(n²) a una O(n log n).

4. Recursión: elegancia con letra pequeña¶

La recursión es una función que se llama a sí misma sobre una versión más pequeña del problema. Es la forma natural de expresar divide y vencerás y cualquier estructura autosemejante (árboles, por ejemplo). Toda recursión necesita dos cosas, o es un desastre:

Caso base: la versión tan pequeña que se resuelve sin recursión. Es lo que garantiza la terminación.
Paso recursivo: que se llame a sí misma sobre algo estrictamente más pequeño, acercándose al caso base.

function factorial(int $n): int {
    if ($n <= 1) return 1;          // caso base → garantiza que termina
    return $n * factorial($n - 1);  // paso: n! = n × (n-1)!, sobre algo menor
}

La letra pequeña, que conecta con la primera lección: cada llamada recursiva apila un stack frame. Una recursión sin caso base, o demasiado profunda, desborda el stack (stack overflow). Por eso hay problemas donde un bucle es preferible a la recursión: mismo resultado, sin arriesgar el stack. La recursión es una herramienta de expresividad, y tiene un coste de memoria que hay que tener presente.

Recursión que repite trabajo: la trampa exponencial

La sucesión de Fibonacci recursiva ingenua (fib(n) = fib(n-1) + fib(n-2)) recalcula los mismos valores una y otra vez → O(2ⁿ), inviable a partir de n≈40. Guardar los resultados ya calculados (memoización, un canje tiempo↔espacio) lo baja a O(n). Reconocer "estoy recalculando lo mismo" es la puerta a la programación dinámica, que verás más adelante.

5. Greedy vs. programación dinámica: dos maneras de decidir¶

Cuando un problema pide la mejor solución (el camino más corto, el máximo beneficio, el mínimo de monedas), hay dos estrategias que conviene distinguir de intuición:

Voraz (greedy): en cada paso, coge lo que parece mejor ahora mismo y no mires atrás. Rápido y simple. Funciona solo si las decisiones locales óptimas construyen la global óptima —lo cual no siempre pasa. Dar el cambio con las monedas más grandes primero es greedy y funciona con el euro; con sistemas de monedas raros, falla.
Programación dinámica (DP): cuando las decisiones se afectan entre sí, exploras las combinaciones pero guardas los subresultados para no recalcularlos (memoización). Más costosa que greedy, pero encuentra el óptimo real donde greedy se equivoca.

No hace falta dominarlas ahora; sí interiorizar la señal: greedy es tentador y a veces mentiroso; cuando las decisiones se interfieren, sospecha que necesitas DP.

6. Grafos: BFS y DFS, recorrer lo conectado¶

Muchísimos problemas son en realidad un grafo: nodos conectados por aristas (redes sociales, mapas de carreteras, dependencias entre tareas, el propio enrutado de internet). Recorrerlos tiene dos formas fundamentales:

BFS (búsqueda en anchura): explora por capas, todos los vecinos antes de ir más lejos. Usa una cola (FIFO). Encuentra el camino con menos saltos —por eso es la base del "grado de separación" y del camino más corto en aristas sin peso.
DFS (búsqueda en profundidad): tira por una rama hasta el fondo antes de retroceder. Usa una pila (o la recursión, que es una pila implícita). Ideal para explorar todo, detectar ciclos, ordenar dependencias.

graph TB
  subgraph "BFS: por capas (cola)"
    R1["A"] --> R2["B"] 
    R1 --> R3["C"]
    R2 --> R4["D"]
    R3 --> R5["E"]
  end

Fíjate en el detalle bonito que cierra la Capa 0: BFS usa una cola y DFS usa una pila —las mismas estructuras de la lección 2—, y DFS es recursión —la de esta lección—, que por debajo es el stack de llamadas —la de la lección 1. Todo se conecta. Esa es la idea de "cimientos": no son temas sueltos, son la misma máquina vista desde distintos ángulos.

Cómo se ve en la práctica¶

No implementas sort, pero eliges y razonas constantemente:

// Tienes 1.000.000 de productos y consultas "¿existe el SKU X?" millones de veces.

// Opción A: búsqueda lineal sobre el array. O(n) por consulta → inviable en bucle.
foreach ($productos as $p) { if ($p->sku === $buscado) return $p; }

// Opción B: ordenar una vez O(n log n) + búsqueda binaria O(log n) por consulta.
//           Buena si consultas mucho y los datos cambian poco.

// Opción C: meterlos en un hash una vez O(n) + acceso O(1) por consulta.
//           La mejor si solo necesitas "¿existe?" / "dame por clave".
$porSku = [];
foreach ($productos as $p) { $porSku[$p->sku] = $p; }
$resultado = $porSku[$buscado] ?? null;   // O(1)

Elegir entre A, B y C es aplicar esta lección: reconocer el patrón (búsqueda), conocer el coste de cada estrategia, y decidir según lo que harás más. Si además necesitaras rangos ("SKUs entre X e Y ordenados"), volverías a la binaria/árbol. El criterio sale de entender los algoritmos, no de memorizarlos.

Lo que sacrificas / errores comunes¶

Buscar el algoritmo "óptimo" cuando n es pequeño. Para 20 elementos, el O(n²) más tonto es instantáneo y más legible. La complejidad importa a escala; por debajo, prima la claridad.
Usar búsqueda binaria sobre datos sin ordenar. Da resultados incorrectos silenciosamente. La precondición (orden) es parte del algoritmo.
Recursión sin vigilar la profundidad. Elegante hasta que stack overflow. Para profundidades grandes o datos hostiles, itera.
Aplicar greedy sin comprobar que da el óptimo. Es rápido y a menudo casi correcto, que es la peor clase de bug: pasa los tests fáciles.
No reconocer que un problema es un grafo. "Dependencias entre tareas", "amigos de amigos", "rutas": si hay cosas conectadas, probablemente es BFS/DFS, y reinventarlo a mano sale mal.

Resumen¶

Un algoritmo se juzga por tres cosas: correctez (bien para toda entrada), terminación (siempre acaba) y coste. La herramienta para argumentar correctez es el invariante.
Búsqueda: lineal O(n) siempre; binaria O(log n) pero exige datos ordenados.
Ordenación: los buenos ordenamientos son O(n log n), y eso es un suelo teórico para ordenar comparando.
Divide y vencerás (partir/resolver/combinar) y recursión (caso base + paso menor) son los patrones que hacen aparecer el log n; ojo al stack y al trabajo repetido (memoización).
Greedy decide local y a veces miente; DP guarda subresultados para el óptimo real. Grafos: BFS (cola, camino más corto en saltos) y DFS (pila/recursión, explorar a fondo) — y todo se apoya en las lecciones anteriores.

Ejercicios socráticos¶

Razónalos con toda la Capa 0. No busques fuera.

La búsqueda binaria encuentra un elemento entre mil millones en ~30 pasos, la lineal en hasta mil millones. ¿Cuál es el peaje que paga la binaria para lograrlo, y qué le pasa si ese peaje no se cumple? Relaciónalo con por qué las BD mantienen índices ordenados.
Explica, sin fórmulas, por qué merge sort es O(n log n): ¿de dónde sale el log n y de dónde el n? ¿Qué patrón general está aplicando?
La función fib recursiva ingenua es O(2ⁿ). ¿Qué está haciendo mal exactamente (qué desperdicia)? ¿Qué técnica lo baja a O(n) y qué canje hace? Conéctalo con la complejidad espacial de la lección anterior.
Tienes que ordenar tareas respetando "la tarea A debe ir antes que la B". ¿Es esto una búsqueda, una ordenación normal, o un grafo? ¿Qué recorrido usarías y por qué? (Pista: dependencias.)
Un compañero implementa "dar el cambio con el mínimo número de monedas" cogiendo siempre la moneda más grande posible (greedy). Funciona con euros. ¿Por qué podría fallar con otro sistema de monedas, y qué enfoque garantizaría el óptimo? ¿Qué te enseña esto sobre confiar en greedy?

Repaso espaciado¶

A Anki (repasos.md).

[ ] ¿Qué precondición exige la búsqueda binaria y por qué le da O(log n)? ¿Qué pasa si no se cumple?
[ ] ¿Por qué ningún ordenamiento por comparación baja de O(n log n)? (La idea de la cota inferior.)
[ ] Describe divide y vencerás en una frase y di por qué produce un factor log n.
[ ] ¿Qué dos partes necesita toda recursión y qué garantiza cada una? ¿Qué riesgo de la lección de memoria tiene?
[ ] BFS vs DFS: qué estructura usa cada uno y para qué tipo de problema es mejor cada uno.

Para seguir tirando del hilo¶

Grokking Algorithms (Bhargava) — búsqueda binaria, ordenación, recursión, grafos y greedy/DP, todo con dibujos. La forma más amable de asentar esta lección.
The Algorithm Design Manual (Skiena) — cuando quieras el "¿qué algoritmo aplico a este problema real?" con catálogo y criterio.
Experimento: implementa búsqueda lineal vs binaria y merge sort vs burbuja, y cronométralos al crecer n. Ver el O(log n) y el O(n log n) ganar en vivo cierra la Capa 0 con los pies en el suelo.

Fin de la Capa 0 · Cimientos

Con esto tienes los cuatro pilares: cómo ejecuta la máquina, cómo colocas los datos, cómo predecir el coste y cómo atacar y razonar los problemas. Todo lo que viene —bases de datos, arquitectura, sistemas distribuidos— se apoya aquí. Cuando estos cuatro estén asentados (no solo leídos), toca la Capa 1.