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 nagyságrendű műveletet végez (ahol egy bizonyos bonyolultsági osztályba tartozik).

Formálisan a mester-tétel azt mondja ki, hogy ha a T függvényt a rekurzív reláció definiálja, amiben és , akkor

  1. , ha
  2. , ha
  3. , ha és valamilyen konstansra és elég nagy n-re.

Az összefüggés akkor is igaz marad, ha helyett vagy á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 rekurzív képlettel írható le, amiből a tétel alapjá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 futásidő adódik.
  • az összefésüléses rendezés is kétszer hívódik meg feleakkora bemenetre, de lépést végez mellette, a teljes futásidő így

Megjegyzések[szerkesztés]

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

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 -nek vesszük a felső vagy az alsó egészrészét, például , akkor az tekinthető -nek.
  • Az ordo jelölésben mindegy, hogy melyik logaritmust használjuk; a   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:

Általánosítás[szerkesztés]

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

Legyen a vizsgált leképezés,

,

ahol , és ahol .

-t implicit módon fejezzük ki vagy minden -re.

Ekkor:

Forrás[szerkesztés]

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