Notación Big O, Estructuras de Datos y Concurrencia

Entender la complejidad temporal, las estructuras de datos y la concurrencia son habilidades fundamentales para cualquier ingeniero de software.

Notación Big O

Big O describe cómo escala el rendimiento de un algoritmo cuando crece la entrada.

Complejidades Comunes

Tiempo
 ↑
 │         O(2ⁿ)  /
 │              /
 │    O(n²)  /
 │         /
 │  O(n log n)
 │    O(n) ──────
 │  O(log n) ───
 │  O(1) ────────
 └──────────────→ Tamaño de entrada (n)

Reglas

1. Eliminar constantes: O(2n) → O(n)
2. Eliminar términos menores: O(n² + n) → O(n²)
3. Enfocarse en el peor caso

Estructuras de Datos

Arrays / Listas

arr = [10, 20, 30, 40, 50]

Listas Enlazadas

Cada nodo apunta al siguiente.

[10] → [20] → [30] → [40] → None

Pilas (LIFO)

pila = []
pila.append(1)   # push
pila.append(2)
pila.pop()       # retorna 2

Casos de uso: Operaciones deshacer, call stack, parsing.

Colas (FIFO)

from collections import deque
cola = deque()
cola.append(1)     # enqueue
cola.popleft()     # dequeue

Casos de uso: Programación de tareas, BFS, colas de mensajes.

Hash Maps / Diccionarios

cache = {"user:1": "Alice", "user:2": "Bob"}

Cómo funciona: Una función hash mapea claves a índices de array. Las colisiones se manejan con chaining o open addressing.

Árboles

Árbol Binario de Búsqueda (BST)

        8
       / \
      3   10
     / \    \
    1   6    14

Árboles Balanceados (AVL, Red-Black)

Auto-balanceados → siempre O(log n) en operaciones.

Heaps

Un árbol binario completo donde el padre siempre es menor (min-heap) o mayor (max-heap).

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappop(heap)  # retorna 1 (el menor)

Casos de uso: Colas de prioridad, problemas top-K.

Grafos

Nodos conectados por aristas.

# Lista de adyacencia
grafo = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

Algoritmos: BFS (camino más corto), DFS (explorar todo), Dijkstra (caminos con peso).

Hashing

Funciones Hash

Mapean datos de cualquier tamaño a un valor de tamaño fijo:

hash("hello")  # → entero

Propiedades:

• Misma entrada → misma salida (determinista)
• Pequeño cambio en entrada → salida muy diferente
• Rápido de calcular

Casos de uso: Diccionarios, cachés, checksums, almacenamiento de contraseñas.

Concurrencia

Conceptos Clave

Concurrencia en Python

# Threading — bueno para tareas I/O-bound
import threading

def fetch_data(url):
    response = requests.get(url)
    return response.json()

threads = [threading.Thread(target=fetch_data, args=(url,))
           for url in urls]
for t in threads: t.start()
for t in threads: t.join()

# Multiprocessing — bueno para tareas CPU-bound
from multiprocessing import Pool

with Pool(4) as p:
    results = p.map(process_item, items)

# Async — bueno para muchas operaciones I/O
import asyncio

async def fetch(url):
    async with aiohttp.ClientSession() as session:
        async with session.get(url) as resp:
            return await resp.json()

results = asyncio.run(asyncio.gather(*[fetch(u) for u in urls]))

Cuándo Usar Qué

Resumen