Algoritmos Esenciales (CLRS)

Cheatsheet Content

Análisis de Algoritmos Notación Asintótica: $O(g(n))$: Cota superior (peor caso). $f(n) \in O(g(n))$ si $f(n) \le c \cdot g(n)$ para $n \ge n_0$. $\Omega(g(n))$: Cota inferior (mejor caso). $f(n) \in \Omega(g(n))$ si $f(n) \ge c \cdot g(n)$ para $n \ge n_0$. $\Theta(g(n))$: Cota ajustada (promedio). $f(n) \in \Theta(g(n))$ si $c_1 g(n) \le f(n) \le c_2 g(n)$ para $n \ge n_0$. $o(g(n))$: Cota superior no ajustada. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$. $\omega(g(n))$: Cota inferior no ajustada. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$. Maestro (Divide y Vencerás): Para $T(n) = aT(n/b) + f(n)$ Caso 1: Si $f(n) = O(n^{\log_b a - \epsilon})$ para $\epsilon > 0$, entonces $T(n) = \Theta(n^{\log_b a})$. Caso 2: Si $f(n) = \Theta(n^{\log_b a} \log^k n)$ para $k \ge 0$, entonces $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. Caso 3: Si $f(n) = \Omega(n^{\log_b a + \epsilon})$ para $\epsilon > 0$ Y $af(n/b) \le c f(n)$ para $c Estructuras de Datos Fundamentales Pilas y Colas: Pila (LIFO): $PUSH(S, x)$, $POP(S)$. $O(1)$ tiempo. Cola (FIFO): $ENQUEUE(Q, x)$, $DEQUEUE(Q)$. $O(1)$ tiempo. Listas Enlazadas: Simple, Doble. $SEARCH(L, k)$, $INSERT(L, x)$, $DELETE(L, x)$. $O(n)$ o $O(1)$ (si el puntero está dado). Tablas Hash: Función Hash: $h(k)$. Resolución de colisiones (Encadenamiento, Direccionamiento Abierto). Rendimiento promedio: $O(1)$ para búsqueda, inserción, eliminación. Peor caso: $O(n)$. Árboles Binarios de Búsqueda (ABB): Propiedad: Elementos en el subárbol izquierdo $\le$ raíz $\le$ elementos en el subárbol derecho. $SEARCH(T, k)$, $INSERT(T, x)$, $DELETE(T, x)$, $MIN(T)$, $MAX(T)$, $SUCCESSOR(T, x)$, $PREDECESSOR(T, x)$. Rendimiento: $O(h)$, donde $h$ es la altura del árbol. Peor caso $O(n)$. Árboles Rojinegros: ABB auto-balanceado. Altura $O(\log n)$. Todas las operaciones: $O(\log n)$. Propiedades: Raíz Negra. Hojas NULAS Negras. Si un nodo es Rojo, sus hijos son Negros. Todo camino simple de un nodo a una hoja NULA contiene el mismo número de nodos negros. Montículos (Heaps): Max-Heap: Padre $\ge$ Hijos. Min-Heap: Padre $\le$ Hijos. Representado por un arreglo. $BUILD-MAX-HEAP(A)$: $O(n)$. $HEAP-MAXIMUM(A)$: $O(1)$. $EXTRACT-MAX(A)$: $O(\log n)$. $INCREASE-KEY(A, i, k)$: $O(\log n)$. $INSERT(A, k)$: $O(\log n)$. Disjoint Sets (Union-Find): $MAKE-SET(x)$, $FIND-SET(x)$, $UNION(x, y)$. Con heurísticas de unión por rango/tamaño y compresión de caminos: casi $O(1)$ amortizado (función inversa de Ackermann, $\alpha(n)$). Algoritmos de Ordenamiento Algoritmo Mejor Caso Caso Promedio Peor Caso Espacio Notas Inserción $\Theta(n)$ $\Theta(n^2)$ $\Theta(n^2)$ $O(1)$ Bueno para datos casi ordenados. Selección $\Theta(n^2)$ $\Theta(n^2)$ $\Theta(n^2)$ $O(1)$ No es estable. Burbuja $\Theta(n)$ $\Theta(n^2)$ $\Theta(n^2)$ $O(1)$ Simple, pero ineficiente. Merge Sort $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n)$ Divide y vencerás. Estable. Heap Sort $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n \log n)$ $O(1)$ Basado en montículo. No es estable. Quick Sort $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $O(\log n)$ (promedio) Divide y vencerás. In-place. Rápido en la práctica. Counting Sort $\Theta(n+k)$ $\Theta(n+k)$ $\Theta(n+k)$ $\Theta(n+k)$ Para enteros en un rango $[0, k]$. Estable. Radix Sort $\Theta(d(n+k))$ $\Theta(d(n+k))$ $\Theta(d(n+k))$ $\Theta(n+k)$ Para enteros con $d$ dígitos, cada uno en rango $[0, k]$. Estable. Programación Dinámica Características: Subproblemas óptimos superpuestos. Estructura de subproblemas óptima. Pasos: Caracterizar la estructura de una solución óptima. Definir el valor de una solución óptima recursivamente. Calcular el valor de una solución óptima (generalmente de abajo hacia arriba). Construir una solución óptima a partir de la información calculada. Ejemplos: Corte de Varilla: $R_n = \max_{1 \le i \le n} (p_i + R_{n-i})$. Multiplicación de Cadenas de Matrices: $m[i,j] = \min_{i \le k Subsecuencia Común Más Larga (LCS). Problema de la Mochila 0/1. Algoritmos Voraces Características: Propiedad de elección voraz: Una elección localmente óptima conduce a una solución globalmente óptima. Subestructura óptima. Pasos: Reformular el problema en términos de subproblemas. Demostrar que es una elección voraz segura. Demostrar subestructura óptima. Desarrollar un algoritmo recursivo que implemente la elección voraz. Convertir el algoritmo recursivo en un algoritmo iterativo. Ejemplos: Selección de Actividades. Códigos Huffman. Árbol de Expansión Mínima (MST): Algoritmos de Prim y Kruskal. Caminos más cortos de una sola fuente (Grafo sin pesos negativos): Algoritmo de Dijkstra. Algoritmos de Grafos Representaciones: Lista de Adyacencia: $O(V+E)$ espacio. Bueno para grafos dispersos. Matriz de Adyacencia: $O(V^2)$ espacio. Bueno para grafos densos. Recorridos: BFS (Búsqueda en Amplitud): Encuentra el camino más corto en grafos no ponderados. Tiempo: $O(V+E)$. DFS (Búsqueda en Profundidad): Clasificación topológica, componentes fuertemente conectados. Tiempo: $O(V+E)$. Árbol de Expansión Mínima (MST): Kruskal: Ordena aristas por peso. Usa Union-Find para evitar ciclos. Tiempo: $O(E \log E)$ o $O(E \log V)$. Prim: Crece un MST desde un vértice inicial usando una cola de prioridad. Tiempo: $O(E \log V)$ con un montículo binario; $O(E + V \log V)$ con un montículo de Fibonacci. Caminos Más Cortos: Una Sola Fuente: Bellman-Ford: Grafos con pesos negativos. Detecta ciclos negativos. $O(VE)$. Dijkstra: Grafos con pesos no negativos. $O(E \log V)$ con montículo binario; $O(E + V \log V)$ con montículo de Fibonacci. DAG (Grafos Acíclicos Dirigidos): Ordenamiento topológico + relajación. $O(V+E)$. Todos los Pares: Floyd-Warshall: $O(V^3)$. Permite pesos negativos pero no ciclos negativos. Johnson: Para grafos dispersos con pesos negativos (reponderación). $O(VE + V^2 \log V)$. Flujo Máximo: Ford-Fulkerson: Algoritmo genérico. Depende de cómo se elijan los caminos de aumento. Edmonds-Karp: Caso especial de Ford-Fulkerson usando BFS para encontrar caminos de aumento. $O(VE^2)$. Algoritmos de Cadenas Algoritmo de Rabin-Karp: Búsqueda de patrones usando hashing. Tiempo promedio: $O(n+m)$. Peor caso: $O(nm)$. Algoritmo Knuth-Morris-Pratt (KMP): Búsqueda de patrones lineales. Usa una función de prefijo para evitar retrocesos. Tiempo: $O(n+m)$. Conceptos Avanzados NP-Completitud: Clase P: Problemas resolubles en tiempo polinomial. Clase NP: Problemas cuyas soluciones pueden verificarse en tiempo polinomial. NP-Completo (NPC): Problemas en NP tal que cualquier problema en NP puede reducirse a él en tiempo polinomial. NP-Hard: Problemas al menos tan difíciles como los problemas NPC. Algoritmos de Aproximación: Para problemas NP-Hard. Garantizan una solución dentro de un factor de la óptima. Algoritmos Probabilísticos y Aleatorizados: Utilizan la aleatoriedad para mejorar el rendimiento o simplificar el algoritmo. Ej: Quicksort (promedio $O(n \log n)$), Prueba de primalidad de Miller-Rabin.