Divide y vencerás
El método de divide y vencerás es un método que permite, en ocasiones, encontrar soluciones efectivas a problemas algorítmicos. La idea es cortar el problema inicial, de tamaño. no, en varios subproblemas más pequeños, luego recombine 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 puede dividir 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 de dividir y conquistar, necesitamos encontrar un programa matemático que nos permita reescribir nuestro problema en subproblemas equivalentes. Dado que este es un método recursivo, no olvide incluir un estado final. Por tanto, estamos 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 es 0 (log n) - tamaño del árbol binario completo en no tapas.
ES 
FR 
EN