Complejidad Algorítmica

El orden típico de complejidad, de menor a mayor, es: Θ(1) < Θ(log n) < Θ(n) < Θ(n log n) < Θ(n²) < Θ(n³) < Θ(2ⁿ) < Θ(n!).

• Θ(n): Recorrer un vector una vez.
• Θ(n²): Bucles anidados.
• Θ(log n): Dividir entre 2 repetidamente.

Estrategias de Diseño

Divide y Vencerás

Divide el problema en varios subproblemas, los resuelve recursivamente y combina las soluciones. Se aplica en algoritmos como MergeSort o Quicksort. Su forma típica es T(n) = aT(n/b) + f(n).

Reducción y Vencerás

Continúa con un único subproblema reducido. Es la base de la búsqueda binaria, que requiere un vector ordenado, con un tiempo de Θ(log n) y un espacio de Θ(1) (iterativo) o Θ(log n) (recursivo).

Teorema Maestro

Para la recurrencia T(n) = aT(n/b) + f(n), se compara f(n) con n^(log_b a):

• Caso 1: Si f(n) crece menos, gana n^(log_b a).
• Caso 2: Si son iguales, aparece un factor log n.
• Caso 3: Si f(n) crece más, gana f(n) (si cumple regularidad).

Algoritmos de Ordenación y Selección

• MergeSort: Divide en dos mitades, ordena recursivamente y fusiona. Coste Θ(n log n) en todos los casos. Es estable y requiere espacio auxiliar Θ(n).
• Quicksort: Utiliza un pivote para particionar. Coste medio Θ(n log n), peor caso Θ(n²). Es eficiente en la práctica, aunque no es estable por defecto.
• Quickselect: Encuentra el k-ésimo elemento sin ordenar todo el conjunto. Caso medio Θ(n), peor caso Θ(n²).

Backtracking y Ramificación

Backtracking (Vuelta atrás)

Explora un árbol de decisiones (normalmente mediante DFS) para problemas de decisión o enumeración (ej. N reinas, Sudoku). Utiliza poda por factibilidad y poda por optimalidad para descartar ramas inútiles.

Ramificación y Poda (Branch & Bound)

Ideal para problemas de optimización (TSP, mochila). Utiliza una lista de nodos vivos y una cota para descartar soluciones que no mejoran la actual. El método Best-First expande el nodo más prometedor.

Algoritmos Voraces y Programación Dinámica

Algoritmos Voraces

Toman la mejor decisión local en cada paso. Garantizan el óptimo solo si existe una propiedad voraz adecuada (ej. Mochila continua, Kruskal, Prim).

Programación Dinámica

Resuelve problemas con subestructura óptima y subproblemas solapados. Puede ser Top-Down (memoización) o Bottom-Up (tabulación).

Grafos y Estructuras Especiales

• Árbol de Recubrimiento Mínimo: Conecta todos los nodos con coste mínimo. Kruskal ordena aristas, mientras que Prim expande el árbol desde un vértice.
• Montículos (Heaps): Árboles binarios completos usados para colas de prioridad. Heapsort aprovecha esta estructura para ordenar en Θ(n log n) de forma in situ.