3.1. Método general.
Para que pueda aplicarse la técnica divide y vencerás necesitamos:
- Normalmente los subproblemas deben ser de tamaños parecidos. Como mínimo necesitamos que hayan dos subproblemas. Si sólo tenemos un solo subproblema entonces hablamos de técnicas de reducción (o simplificación).
- Necesitamos un método (más o menos directo) de resolver los problemas de tamaño pequeño.
- Es necesario tener un método de combinar los resultados de los subproblemas.
3.2. Análisis de tiempos de ejecución.
- Para el esquema recursivo, con división en dos subproblemas:
g(n) Si n?n0 es suficientemente pequeño
2*t(n/2) + f(n) En otro caso
- t(n): tiempo de ejecución del algoritmo.
- g(n): tiempo de calcular la solución para el caso base
- f(n): tiempo adicional de dividir el problema y combinar los resultados.