Glosario — Estructuras de Datos y Algoritmos

A

Algoritmo. Procedimiento finito y no ambiguo que resuelve un problema. En este libro nos importa: correctitud + complejidad.

Análisis amortizado. Costo promedio de una operación cuando se ejecutan muchas seguidas, incluso si una individual puede ser cara. Ejemplo: list.append en Python es $O(1)$ amortizado aunque ocasionalmente sea $O(n)$ (al crecer el array).

Árbol. Grafo conexo, dirigido o no, sin ciclos. Tiene una raíz y nodos con relación padre/hijo.

Árbol binario. Cada nodo tiene a lo sumo 2 hijos.

Árbol BST (Binary Search Tree). Árbol binario donde para cada nodo, todos los del subárbol izquierdo son menores y todos los del derecho mayores.

AVL. BST balanceado: la diferencia de altura entre subárboles izquierdo y derecho es a lo sumo 1. Garantiza operaciones en $O(\log n)$.

B

Backtracking. Estrategia de resolución por exploración recursiva con "deshacer" cuando una rama no lleva a solución. Sudoku, N-reinas, generación de permutaciones.

Bellman-Ford. Algoritmo de camino mínimo que soporta pesos negativos. $O(VE)$. Detecta ciclos negativos.

BFS (Breadth-First Search). Recorrido por niveles usando cola. $O(V + E)$. Da camino mínimo en grafos no ponderados.

Big-O. Cota superior asintótica del crecimiento de una función. $f(n) = O(g(n))$ si existe $C, n_0$ tal que $f(n) \leq C \cdot g(n)$ para $n \geq n_0$.

Big-Omega ($\Omega$). Cota inferior. $f(n) = \Omega(g(n))$ si $f \geq C g$ para $n$ grandes.

Big-Theta ($\Theta$). Cota apretada. $f(n) = \Theta(g(n))$ si es a la vez $O$ y $\Omega$.

Bloom filter. Estructura probabilística para chequear pertenencia. Falsos positivos posibles, falsos negativos no. Uso de memoria muy compacto.

C

Cache. Almacén rápido de pares clave-valor con descarte cuando se llena. Política común: LRU (Least Recently Used).

Camino. Secuencia de aristas que conectan dos vértices.

Chaining. Estrategia de resolución de colisiones en hash tables: cada bucket es una lista enlazada.

Cola (queue). Estructura FIFO (First-In First-Out). Operaciones: enqueue, dequeue. Implementable con array circular o lista doblemente enlazada.

Cola de prioridad. Cola que devuelve siempre el elemento con mayor (o menor) prioridad. Implementación canónica: heap binario.

Complejidad. Recursos (tiempo, espacio) consumidos por un algoritmo en función del tamaño de entrada.

Componente conexo. Subgrafo maximal conectado.

Cota inferior. Mínimo trabajo que cualquier algoritmo debe hacer para un problema. Ejemplo: ordenar requiere al menos $\Omega(n \log n)$ comparaciones.

D

DAG (Directed Acyclic Graph). Grafo dirigido sin ciclos. Permite orden topológico.

DFS (Depth-First Search). Recorrido a fondo usando pila o recursión. $O(V + E)$. Útil para ciclos, topológico, SCC.

Diccionario. En la mayoría de lenguajes, sinónimo de hash table. En Python, dict garantiza orden de inserción desde 3.7.

Dijkstra. Camino mínimo con pesos no negativos. $O((V+E) \log V)$ con heap.

Doblemente enlazada (lista). Cada nodo apunta al siguiente y al anterior. Permite borrado en $O(1)$ si tenés referencia al nodo.

DP (programación dinámica). Estrategia de resolución que descompone en subproblemas y guarda resultados. Aplica cuando hay subestructura óptima + subproblemas superpuestos.

F

Factor de carga. En hash tables: $\alpha = n/m$ (elementos / buckets). Cuando supera ~0.75, se hace rehash para mantener performance.

FIFO. First-In, First-Out. La política de la cola.

Floyd-Warshall. Camino mínimo entre todos los pares de vértices. $O(V^3)$. Para grafos chicos y densos.

G

Grafo. Par $(V, E)$ con vértices $V$ y aristas $E \subseteq V \times V$.

H

Hash collision (colisión). Dos claves distintas que hashean al mismo bucket. Resolución: chaining u open addressing.

Hash function. Función que mapea claves a enteros (índices de buckets). Una buena hash: rápida, distribuye uniformemente, determinista.

Hashing criptográfico. Hash diseñado para ser uno-a-uno computacionalmente (no factible encontrar dos claves con mismo hash). MD5 (roto), SHA-1 (roto), SHA-256 (en uso).

Heap. Árbol binario completo donde cada nodo es ≤ (min-heap) o ≥ (max-heap) que sus hijos. Operaciones push/pop en $O(\log n)$.

I

In-degree / out-degree. En grafos dirigidos: aristas que entran / salen de un vértice.

Indexación. Acceso por posición en una estructura.

L

LIFO. Last-In, First-Out. La política de la pila.

Lista enlazada. Secuencia donde cada nodo apunta al siguiente. Acceso lineal pero inserción/borrado en $O(1)$ con referencia.

LRU (Least Recently Used). Política de cache que descarta el elemento usado hace más tiempo.

M

Matriz de adyacencia. Representación de grafo con tabla $n \times n$. $O(1)$ chequeo de adyacencia, $O(n^2)$ memoria.

MST (Minimum Spanning Tree). Subgrafo conexo que conecta todos los vértices con peso total mínimo. Algoritmos: Kruskal, Prim.

O

Open addressing. Estrategia de colisión donde, si el bucket está ocupado, se prueba el siguiente. Variantes: linear, quadratic, double hashing.

Orden topológico. Permutación lineal de los vértices de un DAG tal que toda arista va de antes a después. Algoritmo de Kahn.

P

Pila (stack). Estructura LIFO. Operaciones: push, pop, peek. Usada en recursión, parsing, undo.

Probing. Sinónimo de búsqueda en open addressing.

R

Recursión. Función que se llama a sí misma. Necesita caso base. Cada llamada usa frame en el stack: cuidado con RecursionError (Python: límite ~1000).

Recursión amortiguada (memoization). Guardar resultados de subllamadas para evitar recomputarlos. Convierte muchas recursiones exponenciales en polinómicas.

Rehashing. Recrear la tabla con más buckets cuando el factor de carga sube. $O(n)$ en el momento, $O(1)$ amortizado.

S

Set. Conjunto sin duplicados. En Python implementado como hash table sin valores. Operaciones $O(1)$ promedio.

SCC (Strongly Connected Components). En grafo dirigido: subgrafos donde existe camino entre cualquier par. Algoritmos: Kosaraju, Tarjan.

Sliding window. Técnica para problemas sobre subarrays/substrings: una "ventana" que se mueve por el array, manteniendo invariantes. Suele dar $O(n)$.

T

Tabla hash. Estructura que mapea claves a valores en $O(1)$ promedio. La estrella del cap. 4.

Two pointers. Técnica con dos índices que recorren el array en distintas direcciones o velocidades. Útil para problemas ordenados.

Trie. Árbol donde cada nodo es un carácter; un camino raíz-a-hoja es una palabra. $O(L)$ búsqueda, donde $L$ es longitud. Usado en autocompletado.

V

Vértice. Sinónimo de nodo en un grafo.

Símbolos comunes

• $|V|, |E|$ — número de vértices, número de aristas.
• $\alpha$ — factor de carga.
• $h$ — altura de árbol.
• $\Sigma$ — alfabeto.

Falta algo? Avisame.