Algoritmos

Un algoritmo es una secuencia finita y no ambigua de pasos que resuelve un problema. Una receta de cocina es un algoritmo; tu código es un algoritmo. Pero no todos los algoritmos son iguales: algunos resuelven el problema mucho más rápido que otros cuando los datos crecen.

La habilidad central de un ingeniero no es «memorizar algoritmos», es razonar sobre eficiencia: saber cuánto costará, elegir el enfoque correcto y reconocer un algoritmo bueno cuando lo ves.

Complejidad y notación Big-O

Big-O describe cómo crece el tiempo (o memoria) de un algoritmo cuando el tamaño de entrada n crece. No mide segundos: mide la tasa de crecimiento (la tendencia).

💡 Regla mental: con n = 1.000.000, O(log n) hace ~20 pasos, O(n) hace un millón, O(n²) hace un billón. De ahí que elegir el algoritmo importe más que la máquina.

Cómo calcular el Big-O de un algoritmo

1. Cuenta las operaciones dominantes (las que se repiten con n).
2. Ignora las constantes: 2n y 100n son ambas O(n).
3. Quedate con el término dominante: n² + n es O(n²).
4. Bucles anidados multiplican: dos bucles de n anidados → O(n²).

def ejemplo(n):
    total = 0
    for i in range(n):        # O(n)
        total += i
    for i in range(n):        # O(n) → bucles separados suman
        for j in range(n):    #   O(n) → anidados multiplican
            total += i * j
    return total              # O(n) + O(n²) = O(n²)

Complejidad espacial

El Big-O de memoria cuenta cuánto espacio extra necesitas (sin contar la entrada). Un algoritmo in-place usa O(1) extra.

def duplica(arr):
    return [x * 2 for x in arr]   # O(n) memoria extra (nuevo array)

Búsqueda

Búsqueda lineal — O(n)

Recorre todos los elementos hasta encontrar el objetivo. Funciona siempre, sin requisitos.

def buscar_lineal(arr, objetivo):
    for i, x in enumerate(arr):
        if x == objetivo:
            return i
    return -1

buscar_lineal([4, 1, 8, 3, 9], 8)   # 2

Búsqueda binaria — O(log n)

Solo funciona en datos ordenados. Divide el espacio a la mitad en cada paso comparando con el medio.

def buscar_binaria(arr, objetivo):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        medio = (lo + hi) // 2
        if arr[medio] == objetivo:
            return medio
        if arr[medio] < objetivo:
            lo = medio + 1      # descartamos la mitad izquierda
        else:
            hi = medio - 1      # descartamos la mitad derecha
    return -1

buscar_binaria([1, 3, 5, 7, 9, 11, 13], 9)   # 4

Buscar 9 en [1,3,5,7,9,11,13]
  [1,3,5,7,9,11,13]  medio=7 → 9>7 → derecha
  [9,11,13]          medio=11 → 9<11 → izquierda
  [9]                medio=9 → ¡encontrado!

⚠️ Cada paso divide a la mitad: con 1.000.000 de elementos solo necesitas ~20 pasos. Por eso los índices de las bases de datos (página de BBDD) hacen búsquedas O(log n), no O(n).

Ordenamiento (sorting)

Ordenar es tan común que cada lenguaje trae su función (sort() en Python/JS, sort en Go). Pero debes saber qué hay debajo y cuándo importa.

💡 En la práctica: los lenguajes usan una mezcla (por ejemplo, Timsort en Python/Java, introsort en C++/Go). Para arrays casi ordenados, insertion sort es imbatible. Para datos grandes, merge/quick. Los dos de abajo (divide y vencerás) son los importantes.

Merge sort — divide y vencerás

Divide el array en mitades, ordena cada mitad recursivamente y fusiona (merge) las mitades ordenadas.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    medio = len(arr) // 2
    izq = merge_sort(arr[:medio])
    der = merge_sort(arr[medio:])
    return fusionar(izq, der)

def fusionar(izq, der):
    resultado = []
    i = j = 0
    while i < len(izq) and j < len(der):
        if izq[i] <= der[j]:
            resultado.append(izq[i]); i += 1
        else:
            resultado.append(der[j]); j += 1
    resultado.extend(izq[i:])
    resultado.extend(der[j:])
    return resultado

merge_sort([38, 27, 43, 3, 9, 82, 10])   # [3, 9, 10, 27, 38, 43, 82]

La profundidad de recursión es log n y cada nivel hace O(n) trabajo → O(n log n).

Quick sort

Elige un pivote, particiona: menores a un lado, mayores al otro, y repite recursivamente.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivote = arr[len(arr) // 2]
    menores = [x for x in arr if x < pivote]
    iguales = [x for x in arr if x == pivote]
    mayores = [x for x in arr if x > pivote]
    return quick_sort(menores) + iguales + quick_sort(mayores)

quick_sort([38, 27, 43, 3, 9, 82, 10])

Recursión y divide y vencerás

Ya vimos recursión en Programación. Divide y vencerás (divide & conquer) es la técnica que la aprovecha:

1. Divide el problema en subproblemas más pequeños.
2. Conquista cada subproblema recursivamente.
3. Combina las soluciones.

Merge sort y quick sort son divide y vencerás. Otro ejemplo clásico: la potencia rápida (calcular x^n en O(log n)):

def potencia(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        mitad = potencia(x, n // 2)
        return mitad * mitad
    return x * potencia(x, n - 1)

potencia(2, 10)   # 1024

Greedy (voraz)

Un algoritmo greedy toma en cada paso la mejor decisión local, esperando que lleve a la mejor global. No siempre funciona, pero cuando funciona es simple y rápido.

Problema clásico: el cambio de monedas. Dar el menor número de monedas posible.

def cambio_greedy(monto, monedas):
    monedas.sort(reverse=True)
    resultado = []
    for m in monedas:
        while monto >= m:
            resultado.append(m)
            monto -= m
    return resultado

cambio_greedy(36, [25, 10, 5, 1])   # [25, 10, 1]

⚠️ Greedy falla si las monedas fueran [1, 3, 4] y quieres 6: greedy da [4, 1, 1] (3 monedas) pero lo óptimo es [3, 3] (2 monedas). Ahí necesitas programación dinámica.

Programación dinámica (DP)

La programación dinámica resuelve problemas guardando resultados de subproblemas para no recalcularlos (memorización). Se usa cuando el problema tiene subproblemas superpuestos (el mismo subproblema aparece muchas veces) y subestructura óptima (la solución óptima viene de soluciones óptimas de subproblemas).

Fibonacci naive es el ejemplo perfecto de por qué DP existe:

def fib_naive(n):          # O(2ⁿ) — el infierno
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

fib(40) con este código hace miles de millones de llamadas, casi todas repetidas. fib(2) se calcula decenas de veces.

Con memorización (top-down) — O(n)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):           # O(n)
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Iterativo (bottom-up) — O(n), sin recursión

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

El patrón de DP en 3 pasos

1. Define el estado: qué parámetros definen un subproblema (ej: i = posición en el array).
2. Define la transición: cómo un subproblema usa los anteriores (la fórmula recursiva).
3. Define el caso base: cuándo el subproblema es trivial.

Ejemplo clásico: subir escaleras. Puedes subir 1 o 2 escalones a la vez. ¿De cuántas formas llegas al escalón n?

def subir_escaleras(n):
    # formas[i] = formas de llegar al escalón i
    # formas[i] = formas[i-1] + formas[i-2]
    if n <= 2:
        return n
    a, b = 1, 2          # formas de llegar a 1 y 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

subir_escaleras(5)   # 8

💡 Terminología DP: memorización (guardar resultados de arriba hacia abajo), tabulation (llenar una tabla de abajo hacia arriba), estado, transición, caso base. Los problemas de «subarray de máxima suma», «knapsack», «edit distance» y «coin change» son todos DP.

Algoritmos sobre grafos

Son el pan de cada día de los ingenieros de sistemas (rutas, dependencias, redes). Se apoyan en las estructuras de la página anterior.

DFS — Depth-First Search (buscar a lo profundo)

Recorre «bajando» por cada camino antes de volver. Se implementa con recursión o pila explícita.

grafo = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
    "D": ["B", "C", "E"], "E": ["D"],
}

def dfs(nodo, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(nodo)
    print(nodo, end=" ")
    for vecino in grafo[nodo]:
        if vecino not in visitados:
            dfs(vecino, visitados)
    return visitados

dfs("A")   # A B D C E (orden según estructura)

BFS — Breadth-First Search (buscar por niveles)

Recorre por niveles (los más cercanos primero). Se implementa con cola. Sirve para camino más corto en grafos sin peso.

from collections import deque

def bfs(inicio, objetivo):
    cola = deque([inicio])
    visitados = {inicio}
    pasos = 0
    while cola:
        for _ in range(len(cola)):     # procesar nivel completo
            nodo = cola.popleft()
            if nodo == objetivo:
                return pasos
            for vecino in grafo[nodo]:
                if vecino not in visitados:
                    visitados.add(vecino)
                    cola.append(vecino)
        pasos += 1
    return -1

bfs("A", "E")   # 2 (A → D → E)

Dijkstra — camino más corto con pesos

BFS solo sirve si todas las aristas pesan igual. Dijkstra maneja pesos, usando una cola de prioridad (heap): siempre expande el nodo con menor distancia acumulada.

import heapq

def dijkstra(grafo_pesos, inicio):
    dist = {nodo: float("inf") for nodo in grafo_pesos}
    dist[inicio] = 0
    heap = [(0, inicio)]
    while heap:
        d, nodo = heapq.heappop(heap)
        if d > dist[nodo]:
            continue              # ya pasó una mejor ruta
        for vecino, peso in grafo_pesos[nodo].items():
            nueva = d + peso
            if nueva < dist[vecino]:
                dist[vecino] = nueva
                heapq.heappush(heap, (nueva, vecino))
    return dist

grafo_pesos = {
    "A": {"B": 4, "C": 2},
    "B": {"D": 3},
    "C": {"B": 1, "D": 5},
    "D": {},
}
dijkstra(grafo_pesos, "A")   # {'A': 0, 'B': 3, 'C': 2, 'D': 6}

⚠️ Dijkstra no funciona con pesos negativos (ahí se usa Bellman-Ford). Con ciclos negativos, no existe camino más corto definido.

Orden topológico (topological sort)

En un DAG (grafo dirigido acíclico), ordena los nodos de forma que cada tarea venga después de sus dependencias. Es como los builds y los gestores de paquetes deciden el orden de instalación.

def orden_topologico(grafo):
    visitados, orden = set(), []

    def visitar(nodo):
        if nodo in visitados:
            return
        visitados.add(nodo)
        for dep in grafo.get(nodo, []):
            visitar(dep)
        orden.append(nodo)     # después de las dependencias

    for nodo in grafo:
        visitar(nodo)
    return orden

deps = {"A": ["B"], "B": ["C"], "C": []}
orden_topologico(deps)   # ['C', 'B', 'A']

Comparativa

Terminología que debes dominar

💡 NP-completo en una línea: hay una clase de problemas (viajante, knapsack general, SAT) donde no se conoce algoritmo polinómico. Reconocer «esto es NP-completo» te ahorra buscar la solución perfecta: busca la aproximación.

Práctica propuesta

1. Implementa búsqueda binaria en C y en Python. Verifícala con datos ordenados y desordenados.
2. Ordena un array de 10.000 números con sort() del lenguaje y mide con time.
3. Implementa merge_sort y quick_sort a mano. Comprueba que dan lo mismo que sort().
4. Resuelve subir escaleras y knapsack 0/1 con DP (tabulation).
5. En un grafo de ciudades conectadas, encuentra el camino más corto entre dos ciudades con BFS y con Dijkstra.
6. Escribe el orden de instalación de un grafo de dependencias de paquetes (topológico).
7. Haz el problema «Two Sum» (LeetCode 1): busca la solución O(n) con hash table.

Para profundizar

• MIT 6.006 — Intro to Algorithms: curso completo y gratuito de MIT.
• CP-Algorithms: enciclopedia con implementaciones y teoría.
• The Algorithm Design Manual (Skiena): orientado a resolver problemas reales, con videos gratis.
• CSES Problem Set: 300+ problemas graduados con juez automático.
• Visualgo: visualiza cada algoritmo.
• Big-O Cheatsheet: referencia rápida.
• Sigue con 🖥️ Cómo funciona una computadora.