Dividir i vèncer · 2.1
L'esquema de dividir i vèncer
Dividir, resoldre recursivament i combinar. Veuràs l'esquema general i com analitzar-ne el cost amb el teorema mestre.
Conceptes clau
- Divisió en subproblemes
- Cas base
- Combinació
- Cost amb el teorema mestre
α = logb a =
Si k < α: domina la recursió, Θ(nα). Si k = α: hi ha un factor log n de més, Θ(nk log n). Si k > α: domina el treball de cada crida, Θ(nk).