Mester-tétel

A mester-tétel a rekurzív algoritmusok egy gyakran előforduló típusának az aszimptotikus bonyolultságának az elemzésére szolgál. A tétel lazán fogalmazva azt mondja meg, mennyi a teljes futásideje egy olyan algoritmusnak, ami minden lépésben a-szor újra meghívja önmagát b-ed akkora bemenetre, valamint további $f(n)$ nagyságrendű műveletet végez (ahol $f(n)$ egy bizonyos bonyolultsági osztályba tartozik). Formálisan a mester-tétel azt mondja ki, hogy ha a T függvényt a $T(n)=aT\left(\frac{n}{b}\right)+f(n)$ rekurzív reláció definiálja, amiben $a\ge 1$ és $b>1$, akkor

1. $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$, ha $f(n)=O\left(n^{{\log }_b\left(a\right)-ϵ}\right)$
2. $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }^{k+1}n\right)$, ha $f(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }^{k}n\right)$
3. $T(n)=\mathrm{\Theta }\left(f\left(n\right)\right)$, ha $f(n)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$ és $af\left(\frac{n}{b}\right)\le cf(n)$ valamilyen $c<1$ konstansra és elég nagy n-re.

Az összefüggés akkor is igaz marad, ha $T\left(\frac{n}{b}\right)$ helyett $T\left(\lfloor \frac{n}{b}\rfloor \right)$ vagy $T\left(\lceil \frac{n}{b}\rceil \right)$ áll. A tétel néhány alkalmazása:

• a bináris keresés minden lépésben egyszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez; a futásideje így a $T(n)=T(\frac{n}{2})+O(1)$ rekurzív képlettel írható le, amiből a tétel alapján $T(n)=O(\log (n))$ adódik.
• egy teljes bináris fa rekurzív bejárása során az algoritmus kétszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez, amiből $O(n)$ futásidő adódik.
• az összefésüléses rendezés is kétszer hívódik meg feleakkora bemenetre, de $O(n)$ lépést végez mellette, a teljes futásidő így $O(n\log (n))$

Megjegyzések

• Tegyük fel, hogy a rekurziós szabály egy additív konstans erejéig különbözik az eredetitől:

$T(n)=aT(\frac{n}{b}+c)+f(n)$

Ha n elég nagy, akkor mellette eltörpül a c konstans, nagyságrendi változást nem okoz. Ezért számolhatunk c = 0-val.

• Ha $n/b$-nek vesszük a felső vagy az alsó egészrészét, például $T(n)=aT(\lfloor \frac{n}{b}\rfloor )+f(n)$, akkor az tekinthető $\frac{n}{b}$-nek.
• Az ordo jelölésben mindegy, hogy melyik logaritmust használjuk; a $T(n)\in \mathrm{\Theta }(\ln (n))$  logarithmus naturalis, természetes logaritmus helyett gondolhatunk akár kettes, akár tízes alapúra is, mivel ezek csak egy konstans szorzóban különböznek egymástól. Ugyanis:

$\ln (n)={\log }_b(n)=\frac{{\log }_a(n)}{{\log }_a(b)}=c\cdot {\log }_{a}n\in \mathrm{\Theta }({\log }_{a}n)=\mathrm{\Theta }(\lg n)$

Általánosítás

A tétel általánosítása az Akra–Bazzi-tétel. Legyen $T:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ a vizsgált leképezés,

$T(n)=\sum _{i=1}^{m}T\left({\alpha }_{i}n\right)+f(n)$,

ahol ${\alpha }_i\in \mathbb{ℝ}:0<{\alpha }_i<1$, $m\in \mathbb{\mathbb{N}}:m\ge 1$ és $f(n)\in \mathrm{\Theta }(n^k)$ ahol $k\in \mathbb{\mathbb{N}}:k\ge 0$. $T$-t implicit módon fejezzük ki $T(x):=T(\lfloor x\rfloor )$ vagy $T(\lceil x\rceil )$ minden $x\in {\mathbb{ℝ}}^{\mathbb{+}}$-re. Ekkor:

$T(n)\in \{\begin{array}{ll}\mathrm{\Theta }(n^k)& \text{ha }\sum _{i=1}^m({\alpha }_i^k)<1\\ \mathrm{\Theta }(n^k\log n)& \text{ha }\sum _{i=1}^m({\alpha }_i^k)=1\\ \mathrm{\Theta }(n^c)\text{, }\sum _{i=1}^m({\alpha }_i^c)=1& \text{ha }\sum _{i=1}^m({\alpha }_i^k)>1\end{array}$

Források

• Th.H.Cormen/C.E.Leiserson/R.Rivest/C.Stein: Introduction to Algorithms. MIT Press 2002 ISBN 0-262-03293-7