V tomto kurzu se dozvíte, co je hlavní věta a jak se používá k řešení relací opakování.
Hlavní metoda je vzorec pro řešení relací opakování formuláře:
T (n) = aT (n / b) + f (n), kde, n = velikost vstupu a = počet dílčích problémů v rekurzi n / b = velikost každého dílčího problému. Předpokládá se, že všechny dílčí problémy mají stejnou velikost. f (n) = náklady na práci provedenou mimo rekurzivní volání, které zahrnují náklady na rozdělení problému a náklady na sloučení řešení Zde jsou ≧ 1 a b> 1 konstanty a f (n) je asymptoticky pozitivní funkce.
Asymptoticky pozitivní funkce znamená, že pro dostatečně velkou hodnotu n máme f(n)> 0.
Hlavní věta se používá k výpočtu časové složitosti relací rekurence (algoritmy dělení a dobývání) jednoduchým a rychlým způsobem.
Master Theorem
Pokud a ≧ 1a b> 1jsou konstanty a f(n)je asymptoticky pozitivní funkce, pak je časová složitost rekurzivního vztahu dána vztahem
T (n) = aT (n / b) + f (n) kde má T (n) následující asymptotické hranice: 1. Pokud f (n) = O (n log b a-ϵ ), pak T (n ) = Θ (n log b a ). 2. Pokud f (n) = Θ (n log b a ), pak T (n) = Θ (n log b a * log n). 3. Pokud f (n) = Ω (n log b a + ϵ ), pak T (n) = Θ (f (n)). ϵ> 0 je konstanta.
Každou z výše uvedených podmínek lze interpretovat jako:
- Pokud se náklady na řešení dílčích problémů na každé úrovni zvýší o určitý faktor, hodnota
f(n)se stane polynomiálně menší než . Časová složitost je tedy utlačována náklady na poslední úroveň, tj.nlogb anlogb a - Pokud jsou náklady na řešení dílčího problému na každé úrovni téměř stejné, pak hodnota
f(n)bude . Časová složitost bude tedy násobkem celkového počtu úrovní, tj.nlogb af(n)nlogb a * log n - Pokud náklady na řešení dílčích problémů na každé úrovni poklesnou o určitý faktor, hodnota
f(n)se stane polynomiálně větší než . Časová složitost je tedy utlačována cenou .nlogb af(n)
Vyřešený příklad hlavní věty
T (n) = 3T (n / 2) + n2 Zde a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 tj. f (n) <n log b a + ϵ , kde, ϵ je konstanta. Případ 3 zde naznačuje. T (T) = f (n) = Θ (n 2 )
Omezení hlavní věty
Hlavní větu nelze použít, pokud:
- T (n) není monotónní. např.
T(n) = sin n f(n)není polynom. např.f(n) = 2n- a není konstanta. např.
a = 2n a < 1
