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)=a\;T\!\left({\frac {n}{b}}\right)+f(n)$ rekurzív reláció definiálja, amiben $a\geq 1$ és $b>1$, akkor

1. $T(n)=\Theta \left(n^{\log _{b}a}\right)$, ha $f(n)=O\left(n^{\log _{b}\left(a\right)-\epsilon }\right)$
2. $T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)$, ha $f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)$
3. $T(n)=\Theta \left(f\left(n\right)\right)$, ha $f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)$ és $af\left({\frac {n}{b}}\right)\leq 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(\left\lfloor {\frac {n}{b}}\right\rfloor \right)$ vagy $T\left(\left\lceil {\frac {n}{b}}\right\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(\textstyle {\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 {\tfrac {n}{b}}\rfloor )+f(n)$, akkor az tekinthető ${\tfrac {n}{b}}$-nek.
• Az ordo jelölésben mindegy, hogy melyik logaritmust használjuk; a $T(n)\in \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)=\textstyle {\frac {\log _{a}(n)}{\log _{a}(b)}}=c\cdot \log _{a}{n}\in \Theta (\log _{a}{n})=\Theta (\lg {n})$

Általánosítás

A tétel általánosítása az Akra–Bazzi-tétel.

Legyen $T:\mathbb {N} \to \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 {R} :0<\alpha _{i}<1$, $m\in \mathbb {N} :m\geq 1$ és $f(n)\in \Theta (n^{k})$ ahol $k\in \mathbb {N} :k\geq 0$.

$T$-t implicit módon fejezzük ki $T(x):=T(\lfloor x\rfloor )$ vagy $T(\lceil x\rceil )$ minden $x\in \mathbb {R^{+}}$-re.

Ekkor:

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

Források

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