Estoy escribiendo esto como anónimo porque no estoy muy seguro de la respuesta y temo el ridículo de mis compañeros.
Intentaré responder esto a mi leal saber y entender.
Ok, ahora volviendo a la respuesta.
Creo que dividir y conquistar es la división que es más importante. La conquista es solo una ventaja derivada.
1. El primer paso es que necesita resolver los subproblemas en los que se puede dividir su problema principal. Una vez que haya encontrado los subproblemas, se divide la parte y, por lo tanto, la mitad de dividir y conquistar.
2. Lo segundo que necesita es el caso base, la etapa apropiada cuando cree que el subproblema no necesita dividirse más, y está en su capacidad de resolver el problema.
3. La siguiente fase es conquistar, es decir, combinar la solución de subproblemas o encontrar la solución del problema del que surgieron.
La solución obtenida del enfoque de divide y vencerás no siempre tiene que ser más eficiente que el enfoque convencional. Para resaltar esto, tomemos un ejemplo de las series de Fibonacci.
- ¿Cómo se comunican los dispositivos GPS con los servidores?
- ¿Cuáles son algunas características de los datos de imágenes faciales que se pueden utilizar para alimentar los algoritmos de aprendizaje automático?
- ¿Qué es el DP?
- ¿Cuál es el propósito del binario?
- ¿Cómo podemos dividir un conjunto dado de números (posiblemente negativos) en dos partes que tienen el mismo promedio?
Ejemplo de serie de Fibonacci: 1,1,2,3,5,8,13….
matemáticamente se puede representar como
fb (n) = fb (n-1) + fb (n-2), si n> 2
= 1, si n = 1,2
Ahora se nos ha dado el problema de encontrar fb (5)
Hay 2 enfoques para resolver esto, el enfoque de arriba hacia abajo y el enfoque de abajo hacia arriba.
La ecuación anterior se puede reescribir como:
fb (1,2) = 1
fb (n) + fb (n + 1) = fb (n + 2)
entonces fb (1) + fb (2) = fb (3)
fb (2) + fb (3) = fb (4)
fb (3) + fb (4) = fb (5)
fb (4) + fb (5) = fb (6)
El método anterior se puede resolver en el orden O (n)
Ahora veamos el enfoque de divide y vencerás
Hagamos esto usando los 3 pasos anteriores.
Paso 1: Divide – (Lo más importante)
Encontrar el subproblema.
Si observa la primera ecuación de encontrar un número de Fibonacci, se puede ver que el problema de encontrar fb (n) se puede dividir en encontrar 2 subproblemas más pequeños, es decir. encontrando fb (n-1) y fb (n-2). Estos subproblemas más pequeños se pueden dividir en encontrar los subproblemas
fb (n-1) = fb (n-2) + fb (n-3)
fb (n-2) = f (n-3) + fb (n-4)
entonces el código podría ser:
suma = fb (n-1) + fb (n-2)
Paso 2: encontrar la condición base
Para esto, debe analizar qué información tenemos sobre el sistema que estamos tratando de programar. En este caso, es fácil observar que fb (1) = 1 y fb (2) = 1. Este podría ser nuestro caso base.
entonces el código podría ser
si (n == 1 O n == 2)
retorno 1;
Paso (3): combinando soluciones de subproblemas
Si observa el diagrama anterior, el caso base forma la hoja del árbol formada recurriendo a los subproblemas.
Ahora conquistamos combinando soluciones de subproblemas
código
suma de retorno
Entonces combinando 1,2 y 3 obtenemos el siguiente código
int fb (int n)
{
int suma = 0;
si (n == 0 || n == 1)
{
suma = 1; //caso base
}
más
{
suma = fb (n-1) + fb (n-2); // divide (también vencerás)
}
suma de retorno; // devolviendo val a la clase padre
}
Análisis:
Cada paso implica dividir el subproblema en 2 subproblemas de tamaño (n-1) y (n-2) respectivamente. El trabajo realizado en eah subproblem aparte del paso recursivo es fijo y puede realizarse en tiempo constante O (1)
Por lo tanto
T (n) = (n-1) + T (n-2) + O (1)
Para simplificar, se puede ver que T (n-1)> T (n-2)
entonces la ecuación anterior se puede simplificar como:
T (n) = 2T (n-2) + O (1)
que podría considerarse similar a la serie Aritmética
por lo tanto T (n) = O (n ^ 2)
Esto es peor que la forma anterior, pero aún ayuda a comprender el concepto de dividir y conquistar.
También se puede lograr Fibonaci en el orden O (lg n) usando el enfoque de dividir y conquistar. Para saber más sobre esto, puedes leer:
El enésimo número de Fibonacci en O (log N)
Traté de ser lo más claro posible para responder la pregunta. Si quieres que haga alguna edición, menciónalos en la sección de comentarios.
