Divide y vencerás¶
Esta estrategia divide un problema hasta llegar el caso base. Posteriormente resuelve de forma recursiva y luego los combina.
La R.R que da divide y vencerás
\[
T(n) = \begin{cases}
\Theta(1) & \texttt{ si } & n = 1 \\
aT(\frac{n}{b})+D(n)+C(n) && \texttt{En otro caso}
\end{cases}
\]
Donde
- \(a\) es el numero de subproblemas
- \(b\) es el tamaño del subproblema
- \(D(n)\) es el costo de dividir
- \(C(n)\) es el costo de combinar Esta R.R se soluciona por el método del maestro.
Varios apuntes.
- Usualmente las complejidades incluyen log(n)
- La división suele hacerse por indices evitando crear estructuras nuevas
- En Scala vamos utilizar Tuplas y splitAt para hacer la división
- Capturamos los datos con pattern matching
ALgunos algoritmos que usan Divide y Vencerás
- Busqueda binaria
- MergeSOrt
- QuickSort
- Busqueda del maximo
- Entre otros