Mistrovská metoda

Master theorem

#veta Mistrovská metoda

Nechť jsou reálné konstanty,
nechť je kladná funkce jedné proměnné.

Uvažujme rekurentní rovnici kde v argumentu může znamenat i nebo . (tedy nemusí do být definované na celých , ale klidně jen na )

Potom pro :

  • 1 ) Pokud pro nějaké , potom
  • 2 ) Pokud , potom
  • 3 ) Pokud pro nějaké ,
    a pokud existuje a (od nějakého indexu dál platí) takové, že žépotom

  • Tedy v situacích 1-3 porovnáváme s naším viz v přípravě

  • Situace 1: je chováním nad (horní mez), zároveň musíme být od něj trochu "odraženi" ()

  • Situace 2: se trefí přesně do (těsná mez)

  • Situace 3: je chováním pod (dolní mez), zároveň musíme být od něj trochu "odraženi" ()

    • znamená, že nejsložitější je na celém algoritmu ta "režie" , rozdělení a sestavení do dílčích kusů

Příklad 1

Mějme rekurenci Máme
Tudíž řčž

Mocnina u (ten logaritmus) je větší než exponent v (tedy ), tudíž se seshora "odrážíme" od jedničky (jsme v situaci 1)

Tudíž existuje kladné , například , takové že Zde i je stále větší než ,
v Mistrovské metodě jsme proto v první situaci a dostáváme výsledek

Příklad 2

Mějme rekurenci Máme
Tudíž a

Zde je exponent přesně roven ,
v Mistrovské metodě jsme proto v druhé situaci a dostáváme výsledek

Příklad 3

Mějme rekurenci Máme
Tudíž řčž

Mocnina u (ten logaritmus) je menší než , tudíž se zespoda "odrážíme" od jedničky (jsme v situaci 3)

Tudíž existuje kladné , například , takové že Dále
kde za můžeme zvolit například

V Mistrovské metodě jsme proto ve třetí situaci a dostáváme výsledek

Příklad 4

Mějme rekurenci Máme
Tudíž řčž

Mocnina u (ten logaritmus) je menší než , tudíž se zespoda "odrážíme" od dvojky (jsme v situaci 3)

Tudíž existuje kladné takové, že Dále
kde za můžeme zvolit například

V Mistrovské metodě jsme proto ve třetí situaci a dostáváme výsledek

Vytvořeno: 29. 11. 2024, 12:56
Poslední aktualizace: 5. 1. 2026, 12:23