Master Theorem je nástroj používaný k řešení rekurentních vztahů, které vznikají při analýze algoritmů rozděl a panuj. Master Theorem poskytuje systematický způsob řešení rekurentních vztahů ve tvaru:
T(n) = aT(n/b) + f(n)
- kde a, b a f(n) jsou kladné funkce a n je velikost problému. Hlavní věta poskytuje podmínky, aby řešení recidivy bylo ve tvaru O(n^k) pro nějakou konstantu k, a dává vzorec pro určení hodnoty k.
- Pokročilá verze Master Theorem poskytuje obecnější formu věty, která dokáže zpracovat rekurentní vztahy, které jsou složitější než základní forma. Pokročilá verze Master Theorem zvládne opakování s více termíny a složitějšími funkcemi.
- Je důležité poznamenat, že hlavní věta není použitelná pro všechny recidivy a nemusí vždy poskytnout přesné řešení dané recidivy. Je to však užitečný nástroj pro analýzu časové složitosti algoritmů rozděl a panuj a poskytuje dobrý výchozí bod pro řešení složitějších recidiv.
Master Theorem se používá k určení doby běhu algoritmů (algoritmů rozděl a panuj) z hlediska asymptotických zápisů.
Zvažte problém, který je vyřešen pomocí rekurze.
function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>
Výše uvedený algoritmus rozděluje problém na A podproblémy, každý o velikosti n/b, a rekurzivně je řešit, aby se vypočítal problém a práce navíc, která byla pro problém vykonána, je dána f(n), tj. časem na vytvoření podproblémů a zkombinování jejich výsledků ve výše uvedené proceduře.
Takže podle hlavního teorému lze dobu běhu výše uvedeného algoritmu vyjádřit jako:
T(n) = aT(n/b) + f(n)>
kde n = velikost problému
a = počet dílčích problémů v rekurzi a a>= 1
n/b = velikost každého dílčího problému
f(n) = náklady na práci provedenou mimo rekurzivní volání, jako je rozdělení na dílčí problémy a náklady na jejich kombinování za účelem získání řešení.
Ne všechny rekurentní vztahy lze vyřešit pomocí hlavní věty, tj
- T(n) není monotónní, např.: T(n) = sin n
- f(n) není polynom, např.: T(n) = 2T(n/2) + 2n
Tato věta je pokročilou verzí hlavní věty, kterou lze použít k určení doby běhu algoritmů rozděl a panuj, pokud má opakování následující formu: -
kde n = velikost problému
a = počet dílčích problémů v rekurzi a a>= 1
n/b = velikost každého dílčího problému
b> 1, k>= 0 a p je reálné číslo.
Pak,
- pokud a> bk, pak T(n) = θ(nlogbA)
- pokud a = bk, pak
(a) pokud p> -1, pak T(n) = θ(nlogbAlogp+1n)
(b) jestliže p = -1, pak T(n) = θ(nlogbAloglogn)
(c) jestliže p <-1, pak T(n) = θ(nlogbA)
- Pokud k, tedy
(a) jestliže p>= 0, pak T(n) = θ(nklogpn)
(b) jestliže p <0, pak T(n) = θ(nk)
Analýza časové složitosti –
- Příklad-1: Binární vyhledávání – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 a p = 0
bk= 1. Takže a = bka p> -1 [Případ 2.(a)]
T(n) = θ(nlogbAlogp+1n)
T(n) = θ(logn) Příklad-2: Sloučit řazení – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
bk= 2. Takže a = bka p> -1 [Případ 2.(a)]
T(n) = θ(nlogbAlogp+1n)
T(n) = θ(nlogn) Příklad-3: T(n) = 3T(n/2) + n2
a = 3, b = 2, k = 2, p = 0
bk= 4. Takže, a k a p = 0 [Případ 3.(a)]
T(n) = θ(nklogpn)
T(n) = θ(n2)
Příklad-4: T(n) = 3T(n/2) + log2n
a = 3, b = 2, k = 0, p = 2
bk= 1. Takže a> bk[Případ 1]
T(n) = θ(nlogbA)
T(n) = θ(nlog23)
Příklad-5: T(n) = 2T(n/2) + nlog2n
a = 2, b = 2, k = 1, p = 2
bk= 2. Takže a = bk[Případ 2.(a)]
T(n) = θ(nlogbAlogp+1n)
T(n) = θ(nlog22log3n)
T(n) = θ(nlog3n)
Příklad-6: T(n) = 2nT(n/2) + nn
Toto opakování nelze vyřešit pomocí výše uvedené metody, protože funkce není ve tvaru T(n) = aT(n/b) + θ(nklogpn)
GATE Cvičné otázky –
- GATE-CS-2017 (Sada 2) | Otázka 56
- GATE IT 2008 | Otázka 42
- GATE CS 2009 | Otázka 35
Zde je několik důležitých bodů, které je třeba mít na paměti ohledně Master Theorem:
- Opakování rozděl a panuj: Hlavní teorém je speciálně navržen k řešení vztahů opakování, které vznikají při analýze algoritmů rozděl a panuj.
- Forma rekurence: Hlavní věta platí pro rekurentní vztahy ve tvaru T(n) = aT(n/b) + f(n), kde a, b a f(n) jsou kladné funkce a n je velikost problému.
- Časová složitost: Master Theorem poskytuje podmínky pro řešení rekurence ve tvaru O(n^k) pro nějakou konstantu k a dává vzorec pro určení hodnoty k.
- Pokročilá verze: Pokročilá verze Master Theorem poskytuje obecnější formu věty, která dokáže zpracovat rekurentní vztahy, které jsou složitější než základní forma.
- Omezení: Hlavní věta není použitelná pro všechny recidivy a nemusí vždy poskytovat přesné řešení dané recidivy.
- Užitečný nástroj: Přes svá omezení je Master Theorem užitečným nástrojem pro analýzu časové složitosti algoritmů rozděl a panuj a poskytuje dobrý výchozí bod pro řešení složitějších recidiv.
- Doplněno o další techniky: V některých případech může být nutné doplnit Master Theorem o další techniky, jako je substituční metoda nebo iterační metoda, aby se zcela vyřešil daný rekurentní vztah.