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 2: se trefí přesně do (těsná mez)

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

  • 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ž , tudíž se "odrážíme" od jedničky (jsme v situaci 1)

Tudíž existuje kladné , například , takové že V Mistrovské metodě jsme proto v první situaci a dostáváme výsledek

Příklad 2

Mějme rekurenci Máme
Tudíž a

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 "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

Vytvořeno: 29. 11. 2024, 12:56
Poslední aktualizace: 13. 12. 2024, 19:40