În acest tutorial, veți afla ce este teorema master și cum este utilizată pentru rezolvarea relațiilor de recurență.
Metoda master este o formulă pentru rezolvarea relațiilor de recurență ale formei:
T (n) = aT (n / b) + f (n), unde, n = dimensiunea intrării a = numărul de subprobleme din recursivitate n / b = dimensiunea fiecărei subprobleme. Se presupune că toate subproblemele au aceeași dimensiune. f (n) = costul muncii efectuate în afara apelului recursiv, care include costul împărțirii problemei și costul fuzionării soluțiilor Aici, a ≧ 1 și b> 1 sunt constante, iar f (n) este un pozitiv asimptotic funcţie.
O funcție pozitivă asimptotic înseamnă că pentru o valoare suficient de mare de n, avem f(n)> 0.
Teorema master este utilizată în calcularea complexității în timp a relațiilor de recurență (algoritmi divizați și cuceriți) într-un mod simplu și rapid.
Teorema Maestrului
Dacă a ≧ 1și b> 1sunt constante și f(n)este o funcție pozitivă asimptotic, atunci complexitatea în timp a unei relații recursive este dată de
T (n) = aT (n / b) + f (n) unde, T (n) are următoarele limite asimptotice: 1. Dacă f (n) = O (n log b a-ϵ ), atunci T (n ) = Θ (n log b a ). 2. Dacă f (n) = Θ (n log b a ), atunci T (n) = Θ (n log b a * log n). 3. Dacă f (n) = Ω (n log b a + ϵ ), atunci T (n) = Θ (f (n)). ϵ> 0 este o constantă.
Fiecare dintre condițiile de mai sus poate fi interpretată ca:
- Dacă costul rezolvării subproblemelor la fiecare nivel crește cu un anumit factor, valoarea lui
f(n)va deveni polinomial mai mică decât . Astfel, complexitatea timpului este oprimată de costul ultimului nivel, adică.nlogb anlogb a - Dacă costul rezolvării subproblemelor la fiecare nivel este aproape egal, atunci valoarea lui
f(n)va fi . Astfel, complexitatea timpului va fi de două ori numărul total de niveluri, adică.nlogb af(n)nlogb a * log n - Dacă costul rezolvării subproblemelor la fiecare nivel scade cu un anumit factor, valoarea lui
f(n)va deveni polinomial mai mare decât . Astfel, complexitatea timpului este oprimată de costul .nlogb af(n)
Exemplu rezolvat de Teorema Maestrului
T (n) = 3T (n / 2) + n2 Aici, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 adică. f (n) <n log b a + ϵ , unde, ϵ este o constantă. Cazul 3 implică aici. Astfel, T (n) = f (n) = Θ (n 2 )
Limitări ale teoremei maestrului
Teorema master nu poate fi utilizată dacă:
- T (n) nu este monoton. de exemplu.
T(n) = sin n f(n)nu este un polinom. de exemplu.f(n) = 2n- a nu este o constantă. de exemplu.
a = 2n a < 1
