Anàlisi d'algorismes · 1.4
Recurrències i teorema mestre
El cost d'un algorisme recursiu s'expressa amb una recurrència. Aprendràs a resoldre les més habituals, sobretot amb el teorema mestre.
Conceptes clau
- Recurrències substractores
- Recurrències divisores
- Teorema mestre
- Arbre de recursió
α = 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).