Mester-tétel

A Wikipédiából, a szabad enciklopédiából

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  a f\left( \frac{n}{b} \right) \le c f(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[szerkesztés | forrásszöveg szerkesztése]

  • Tegyük fel, hogy a rekurziós szabály egy additív konstans erejéig különbözik az eredetitől:
T(n) = a T(\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) = a T( \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\sdot \log_a{n} \in \Theta( \log_a{n}) = \Theta( \lg{n})

Általánosítás[szerkesztés | forrásszöveg szerkesztése]

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 \ge 1 és f(n) \in \Theta(n^k) ahol k \in \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{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ás[szerkesztés | forrásszöveg szerkesztése]

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