Algoritmos CLRS

Cheatsheet Content

### 1. Fundamentos de Algoritmos - **Notación Asintótica:** - $O(g(n))$: Cota superior asintótica (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 asintótica (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 asintótica. $f(n) \in \Theta(g(n))$ si $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ para $n \ge n_0$. - $o(g(n))$: Cota superior estricta. $f(n)$ crece *estrictamente más lento* que $g(n)$. - $\omega(g(n))$: Cota inferior estricta. $f(n)$ crece *estrictamente más rápido* que $g(n)$. - **Análisis de Complejidad:** - **Tiempo:** Número de operaciones elementales. - **Espacio:** Cantidad de memoria utilizada. - **Recurrencias:** - **Método de Sustitución:** Adivinar solución y probar por inducción. - **Método del Árbol de Recurrencia:** Visualizar y sumar costos por nivel. - **Teorema Maestro:** Para $T(n) = aT(n/b) + f(n)$: 1. Si $f(n) \in O(n^{\log_b a - \epsilon})$ para $\epsilon > 0$, entonces $T(n) \in \Theta(n^{\log_b a})$. 2. Si $f(n) \in \Theta(n^{\log_b a})$, entonces $T(n) \in \Theta(n^{\log_b a} \log n)$. 3. Si $f(n) \in \Omega(n^{\log_b a + \epsilon})$ para $\epsilon > 0$ Y $af(n/b) \le c f(n)$ para $c ### 2. Estructuras de Datos Fundamentales - **Listas Enlazadas:** - **Sencillamente enlazada:** Cada nodo apunta al siguiente. - **Doblemente enlazada:** Cada nodo apunta al anterior y al siguiente. - **Circular:** El último nodo apunta al primero. - **Operaciones (promedio/peor):** Buscar $O(n)$, Insertar $O(1)$, Eliminar $O(1)$ (si se tiene un puntero al predecesor). - **Pilas (Stacks):** LIFO (Last-In, First-Out). - **Operaciones:** PUSH $O(1)$, POP $O(1)$. - **Colas (Queues):** FIFO (First-In, First-Out). - **Operaciones:** ENQUEUE $O(1)$, DEQUEUE $O(1)$. - **Tablas Hash:** Mapeo de claves a valores. - **Función Hash:** $h(k)$. - **Colisiones:** - **Encadenamiento:** Listas enlazadas en cada ranura. - **Direccionamiento Abierto:** Probing (lineal, cuadrático, doble hashing). - **Rendimiento:** - Promedio: Buscar $O(1+\alpha)$, Insertar $O(1+\alpha)$, Eliminar $O(1+\alpha)$, donde $\alpha = n/m$ (factor de carga). - Peor caso: $O(n)$ si todas las claves colisionan. - **Árboles Binarios de Búsqueda (BST):** - Para cada nodo $x$, todos los elementos en el subárbol izquierdo son $\le x$, y todos en el subárbol derecho son $\ge x$. - **Operaciones (altura $h$):** Buscar $O(h)$, Insertar $O(h)$, Eliminar $O(h)$. - Peor caso: $O(n)$ para un árbol degenerado. - **Árboles Rojinegros (Red-Black Trees):** BST auto-balanceados. - **Propiedades:** Cada nodo es rojo o negro. Raíz negra. Hojas NIL negras. Si un nodo es rojo, sus hijos son negros. Todo camino de un nodo a una hoja NIL tiene el mismo número de nodos negros. - **Operaciones:** Todas $O(\log n)$ en el peor caso. - **Montículos (Heaps - Max/Min-Heap):** - Árbol binario casi completo. - **Max-Heap:** Cada nodo es $\ge$ sus hijos. - **Min-Heap:** Cada nodo es $\le$ sus hijos. - **Operaciones:** HEAPIFY $O(\log n)$, BUILD-HEAP $O(n)$, HEAP-EXTRACT-MAX $O(\log n)$, HEAP-INCREASE-KEY $O(\log n)$, HEAP-INSERT $O(\log n)$. ### 3. Algoritmos de Ordenación - **Insertion Sort:** - Compara cada elemento con los anteriores y lo inserta en su posición correcta. - Tiempo: $O(n^2)$ peor/promedio, $O(n)$ mejor. - Espacio: $O(1)$. - Estable, in-place. - **Merge Sort:** - Divide y Vencerás. Divide el array a la mitad, ordena cada mitad recursivamente, y luego las fusiona. - Tiempo: $O(n \log n)$ peor/promedio/mejor. - Espacio: $O(n)$ (por el array auxiliar para la fusión). - Estable. - **Heap Sort:** - Construye un Max-Heap a partir del array, luego extrae el máximo repetidamente y lo coloca al final. - Tiempo: $O(n \log n)$ peor/promedio/mejor. - Espacio: $O(1)$ (in-place). - No estable. - **Quick Sort:** - Divide y Vencerás. Elige un pivote, particiona el array en elementos menores y mayores que el pivote, y ordena recursivamente las sublistas. - Tiempo: $O(n \log n)$ promedio, $O(n^2)$ peor. - Espacio: $O(\log n)$ promedio (por la pila de recursión), $O(n)$ peor. - No estable, in-place. - **Lower Bound para Ordenación por Comparación:** Cualquier algoritmo de ordenación basado en comparaciones tiene un límite inferior de $\Omega(n \log n)$ en el peor caso. - **Counting Sort:** - Para enteros en un rango pequeño $[0, k]$. Cuenta ocurrencias de cada número. - Tiempo: $O(n + k)$. - Espacio: $O(n + k)$. - Estable. - **Radix Sort:** - Ordena números procesando dígitos de derecha a izquierda (o izquierda a derecha) usando un algoritmo de ordenación estable (ej. Counting Sort). - Tiempo: $O(d(n+k))$, donde $d$ es el número de dígitos. - Espacio: $O(n + k)$. - Estable. ### 4. Técnicas de Diseño de Algoritmos - **Divide y Vencerás:** 1. **Divide:** Rompe el problema en subproblemas más pequeños. 2. **Vencerás:** Resuelve los subproblemas recursivamente. Si son lo suficientemente pequeños, resuélvelos directamente. 3. **Combina:** Combina las soluciones de los subproblemas para obtener la solución del problema original. - Ejemplos: Merge Sort, Quick Sort, Búsqueda Binaria. - **Programación Dinámica:** - Para problemas con **subproblemas superpuestos** y **estructura óptima de subproblemas**. - **Enfoque:** Construir la solución a partir de soluciones de subproblemas más pequeños, almacenando los resultados para evitar recálculos (memoización o tabulación). - Ejemplos: Serie de Fibonacci, Coeficientes Binomiales, Problema de la Mochila (0/1), Cadena de Multiplicación de Matrices, Subsecuencia Común Más Larga. - **Algoritmos Voraces (Greedy Algorithms):** - Realiza la elección localmente óptima en cada etapa con la esperanza de que esta elección conduzca a una solución globalmente óptima. - No siempre produce la solución óptima. - Para que funcione, el problema debe exhibir: 1. **Propiedad de elección voraz:** Una solución globalmente óptima puede alcanzarse haciendo una elección localmente óptima. 2. **Estructura óptima de subproblemas.** - Ejemplos: Problema de Selección de Actividades, Algoritmo de Huffman, Algoritmos de Prim y Kruskal para MST. ### 5. Algoritmos de Grafos (Parte 1) - **Representaciones de Grafos:** - **Lista de Adyacencia:** Para cada vértice, una lista de sus vecinos. - $V$ vértices, $E$ aristas. - Espacio: $O(V+E)$. - Bueno para grafos dispersos ($E \ll V^2$). - **Matriz de Adyacencia:** Matriz $V \times V$ donde $M[i][j]=1$ si hay arista $(i,j)$, 0 en caso contrario. - Espacio: $O(V^2)$. - Bueno para grafos densos ($E \approx V^2$). - **Búsqueda en Amplitud (BFS - Breadth-First Search):** - Explora el grafo capa por capa. Usa una cola. - Encuentra la distancia más corta (en número de aristas) desde la fuente. - Tiempo: $O(V+E)$. - **Búsqueda en Profundidad (DFS - Depth-First Search):** - Explora el grafo tan profundo como sea posible antes de retroceder. Usa una pila (implícitamente por recursión). - Útil para encontrar componentes conexas, detección de ciclos, ordenación topológica. - Tiempo: $O(V+E)$. - **Ordenación Topológica:** - Para DAGs (Grafos Acíclicos Dirigidos). - Produce un orden lineal de vértices tal que para cada arista $(u,v)$, $u$ aparece antes que $v$ en el orden. - Puede implementarse con DFS. - Tiempo: $O(V+E)$. ### 6. Algoritmos de Grafos (Parte 2) - **Árboles de Expansión Mínima (MST - Minimum Spanning Tree):** - Para grafos no dirigidos, ponderados. Un subgrafo que es un árbol y conecta todos los vértices con el costo total mínimo de las aristas. - **Algoritmo de Kruskal:** - Ordena todas las aristas por peso. - Itera sobre las aristas, añadiendo la arista más ligera si no forma un ciclo con las aristas ya elegidas (usa una estructura de datos `Union-Find`). - Tiempo: $O(E \log E)$ o $O(E \log V)$. - **Algoritmo de Prim:** - Comienza con un vértice arbitrario. - En cada paso, añade la arista más ligera que conecta un vértice en el MST en construcción con un vértice fuera de él. - Usa una cola de prioridad (Min-Heap). - Tiempo: $O(E \log V)$ o $O(E + V \log V)$ con Fibonacci Heap. - **Caminos Más Cortos de Fuente Única:** - **Algoritmo de Dijkstra:** - Para grafos con pesos de arista no negativos. - Usa una cola de prioridad para extraer el vértice no visitado con la distancia más pequeña. - Tiempo: $O(E \log V)$ o $O(E + V \log V)$ con Fibonacci Heap. - **Algoritmo de Bellman-Ford:** - Para grafos con pesos de arista arbitrarios (positivos o negativos). - Detecta ciclos de peso negativo. - Relaja todas las aristas $V-1$ veces. - Tiempo: $O(VE)$. - **Caminos Más Cortos de Todas las Fuentes (APSP - All-Pairs Shortest Paths):** - **Algoritmo de Floyd-Warshall:** - Programación Dinámica. Considera vértices intermedios $k$. - Calcula $d^{(k)}_{ij}$ como la distancia más corta de $i$ a $j$ usando solo vértices de $\{1, ..., k\}$ como intermedios. - Tiempo: $O(V^3)$. - **Algoritmo de Johnson:** - Re-pondera las aristas para que sean no negativas (usando Bellman-Ford), luego ejecuta Dijkstra para cada vértice. - Tiempo: $O(VE + V^2 \log V)$. ### 7. Complejidad y NP-Completitud - **Clases de Complejidad:** - **P:** Problemas que pueden ser resueltos en tiempo polinomial por una máquina de Turing determinista. - **NP:** Problemas cuyas soluciones pueden ser *verificadas* en tiempo polinomial por una máquina de Turing determinista. - **NP-Hard:** Un problema $H$ es NP-Hard si todo problema en NP se puede reducir a $H$ en tiempo polinomial. - **NP-Completo (NPC):** Un problema $C$ es NP-Completo si $C \in NP$ y $C \in NP-Hard$. - **Reducciones Polinomiales:** $A \le_p B$ significa que el problema $A$ puede ser transformado en el problema $B$ en tiempo polinomial. Si $A \le_p B$ y $B$ es resoluble en tiempo $P$, entonces $A$ también lo es. - **Ejemplos de Problemas NP-Completos:** - Problema del Viajante de Comercio (TSP) - Problema de la Mochila (Knapsack) - Problema del Conjunto Independiente (Independent Set) - Problema de Satisfacibilidad (SAT) - Problema de la Cobertura de Vértices (Vertex Cover)