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

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

Az összefüggés akkor is igaz marad, ha ${\displaystyle T\left({\frac {n}{b}}\right)}$ helyett ${\displaystyle T\left(\left\lfloor {\frac {n}{b}}\right\rfloor \right)}$ vagy ${\displaystyle 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 ${\displaystyle T(n)=T({\frac {n}{2}})+O(1)}$ rekurzív képlettel írható le, amiből a tétel alapján ${\displaystyle 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 ${\displaystyle O(n)}$ futásidő adódik.
• az összefésüléses rendezés is kétszer hívódik meg feleakkora bemenetre, de ${\displaystyle O(n)}$ lépést végez mellette, a teljes futásidő így ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle n/b}$-nek vesszük a felső vagy az alsó egészrészét, például ${\displaystyle T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)}$, akkor az tekinthető ${\displaystyle {\tfrac {n}{b}}}$-nek.
• Az ordo jelölésben mindegy, hogy melyik logaritmust használjuk; a ${\displaystyle 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:

${\displaystyle \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 ${\displaystyle T:\mathbb {N} \to \mathbb {N} }$ a vizsgált leképezés,

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

ahol ${\displaystyle \alpha _{i}\in \mathbb {R} :0<\alpha _{i}<1}$, ${\displaystyle m\in \mathbb {N} :m\geq 1}$ és ${\displaystyle f(n)\in \Theta (n^{k})}$ ahol ${\displaystyle k\in \mathbb {N} :k\geq 0}$.

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

Ekkor:

${\displaystyle 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

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!