Dividir y conquistar

Este método, como dice el nombre, se basa en dividir un problema en subproblemas del mismo tipo pero menor tamaño. La idea central es que los problemas mas pequeños son mas fáciles de resolver que uno grande. Entonces, uno divide el planteo en situaciones mas manejables, y luego las junta para formular la respuesta a la pregunta original.

Por dar algunos ejemplos, el método de ordenamiento Quick sort utiliza una forma de dividir y conquistar. De igual forma, la búsqueda binaria se basa en el mismo concepto.

Esto funciona muy bien pero hay que tener una cosa siempre en claro: los costos de dividir y combinar no pueden ser demasiado costosos. Si vamos a implementar dividir y conquistar vamos a querer que la complejidad se vea reducida, o mínimamente que siga igual.

Según el teorema maestro, los algoritmos de dividir y conquistar poseen una complejidad de $O (n^{\log_{b} a})$ , donde $n$ es el tamaño de la entrada, $a$ es la cantidad de subproblemas en los que la entrada fue dividido. El tamaño de los nuevos subproblemas es de $\frac{n}{b}$ , siempre y cuando $\frac{n}{b} > 0$ .