Divide y vencerás

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

Divide y vencerás

A diferencia de la 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:

  1. 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.
  2. Regla: los subproblemas se resuelven de forma recursiva.
  3. 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.

Un método ingenuo sería hacer un bucle donde a * = x con a = 1 inicialmente. La complejidad del método ingenuo es, por 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:

Divide y conquista la exponenciación rápida

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.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: