Divide y vencerás
Divide el vector, resuelve cada mitad y combina. Sigue el trozo de cada llamada en el vector, en el código y en el árbol.
■ trozo de la llamada · ■ mitad
1int maximo(int V[], int ini, int fin)2{3 int mitad, izq, der;4 if (ini == fin) // caso trivial5 return V[ini];6 mitad = (ini + fin) / 2; // dividir7 izq = maximo(V, ini, mitad); // resolver8 der = maximo(V, mitad + 1, fin);9 return izq > der ? izq : der; // combinar10}Trozo [0..7] con 8 elementos: hay que dividir.
Divide el vector en dos mitades, busca el máximo de cada una y quédate con el mayor. Un solo elemento es su propio máximo.
| Recurrencia | T(n) = 2·T(n/2) + O(1) |
| Coste | O(n): n − 1 comparaciones, las mismas que un bucle |
Divide y vencerás es un esquema de diseño de algoritmos: si el problema es trivial se resuelve directamente; si no, se divide en subproblemas del mismo tipo más pequeños, se resuelve cada uno recursivamente y se combinan sus soluciones.
Con vectores, lo habitual es dividir por la mitad con mitad = (ini + fin) / 2 y llamar para [ini..mitad] y [mitad + 1..fin]. El caso trivial es un trozo de un solo elemento. La búsqueda binaria es especial: solo necesita resolver una de las dos mitades.
Elige un problema y sigue el trozo de cada llamada en el vector y en el árbol de subproblemas. En el panel de coste verás la ecuación de recurrencia y su solución.
Calcula el máximo de V = {4, 9, 2, 7} con divide y vencerás.
- maximo(0, 3): mitad = 1. Llamo a maximo(0, 1) y a maximo(2, 3).
- maximo(0, 1): mitad = 0. maximo(0, 0) = 4 y maximo(1, 1) = 9, así que devuelve 9.
- maximo(2, 3): maximo(2, 2) = 2 y maximo(3, 3) = 7, así que devuelve 7.
- Combino: max(9, 7) = 9. Ha habido 7 llamadas y 3 comparaciones.
El máximo es 9
Preguntas frecuentes
¿Es más rápido buscar el máximo con divide y vencerás que con un bucle?
No: los dos hacen n − 1 comparaciones y son O(n). Divide y vencerás gana cuando la combinación aprovecha el trabajo hecho, como en merge sort (O(n log n) frente a O(n²)) o cuando se descarta una mitad, como en la búsqueda binaria.
¿Cómo se calcula el coste de un algoritmo de divide y vencerás?
Con su ecuación de recurrencia. Si se hacen a llamadas de tamaño n/b y el resto cuesta O(1): con a = 2 y b = 2 el coste es O(n), y con a = 1 y b = 2, O(log n).
¿Por qué la búsqueda binaria necesita el vector ordenado?
Porque al comparar x con el elemento central decide en qué mitad puede estar. Sin orden no hay forma de descartar ninguna mitad.
¿Qué pasa con la costura en «¿Creciente?»?
Que las dos mitades sean crecientes no basta: también hay que comprobar que el último elemento de la izquierda sea menor que el primero de la derecha. Esa comprobación es la función de combinación.