Divide y vencerás
El método divide y vencerás es un método que en ocasiones permite encontrar soluciones efectivas a problemas algorítmicos. La idea es recortar el problema inicial, tamaño no, en varios subproblemas de menor tamaño, para luego recombinar las soluciones parciales hasta obtener la solución final.
Principio
A diferencia del programación dinámica, los resultados de los subproblemas solo son útiles para el resultado del problema principal.
El algoritmo divide y vencerás se divide en tres pasos:
- Dividir: el problema se divide en subproblemas de tamaño. b / n. Estos subproblemas son de la misma naturaleza que sus padres. Por tanto, estamos en presencia de Para subproblemas idénticos. Cuando b = 2, estamos hablando de dicotomía.
- Regla: los subproblemas se resuelven de forma recursiva.
- Recombina: las soluciones de los subproblemas se recombinan para reconstruir la solución al problema inicial.
Ejemplo
Para comprender mejor la construcción del algoritmo, tomaremos el ejemplo de exponenciación rápida. El principio de este algoritmo es calcular xno.
Una forma ingenua sería hacer un bucle donde a*= x con a = 1 inicialmente. los complejidad del método ingenuo es por lo tanto lineal 0(n).
Para usar el método divide y vencerás, necesitamos encontrar un programa matemático para reescribir nuestro problema en subproblemas equivalentes. Dado que este es un método recursivo, no olvide incluir un estado final. Estamos por tanto en presencia del siguiente programa matemático:
El algoritmo es como sigue:
doble potencia (doble x, int n) {
tejo (n == 0) devuelve 1;
demás {
tejo (n%2 == 0) retorno de potencia (x * x, n / 2);
demás devuelve x * potencia (x * x, (n-1) / 2);
terminara si
terminara si
}
Su complejidad está en 0 (log n) - tamaño del árbol binario completo en no tapas.
