Master theorem (také Kuchařková věta nebo Mistrovská metoda) je speciální případ Akra-Bazzi theoremu, poskytuje při analýze složitosti algoritmů kuchařkové řešení asymptotické složitosti pro často používané rekurentní vztahy. Byl popularizován knihou Introduction to Algorithms napsanou Cormenem, Leisersonem, Rivestem a Steinem, kde je uveden a dokázán v sekcích 4.3 a 4.4.
Master theorem řeší rekurentní vztahy ve tvaru:
, kde ![{\displaystyle a\geq 1{\mbox{, }}b>1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dabfde41475599f1ee6f394d9d7e2b07de40dc9c)
Při analýze rekurzivních algoritmů mají konstanty a funkce následující význam:
je velikost problému.
je počet podproblémů v rekurzi.
je velikost každého z podproblémů. Předpokládá se, že podproblémy jsou víceméně stejně velké.
je cena práce mimo rekurzivní volání, zahrnující rozdělení problému na podproblémy a sloučení výsledků podproblémů.
Je možné zjistit asymptotickou složitost v následujících třech případech:
Pokud platí, že
pro nějaké
tak:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c76f6a607048e6d072f60093b4a99fceb5841262)
![{\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d86a4deef09a035c732738b1888552d6a6c4e4f7)
Z výše uvedené rovnice vidíme, že hodnoty jsou:
,
,
, ![{\displaystyle \log _{b}a=\log _{2}8=3\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b1c755a574c3907ef537b553343a107d0fb28dd)
Nyní musíme zkontrolovat, zda platí:
![{\displaystyle f(n)={\mathcal {O}}\left(n^{\log _{b}a-\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b7ca78ab1f1d06ac2ab8f762000d443b0602a26)
Po dosazení hodnot dostaneme:
![{\displaystyle 1000n^{2}={\mathcal {O}}\left(n^{3-\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adef8158570b70659c4685b59d8ebd01b4076f93)
Pokud zvolíme
= 1, dostaneme:
![{\displaystyle 1000n^{2}={\mathcal {O}}\left(n^{3-1}\right)={\mathcal {O}}\left(n^{2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca8c66fcb0cc050ad9512e3fff5dc32622ab9061)
Protože rovnost platí, první případ master theoremu lze použít na danou rekurentní rovnost, čímž dostaneme:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c76f6a607048e6d072f60093b4a99fceb5841262)
Po dosazení hodnot:
![{\displaystyle T(n)=\Theta \left(n^{3}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f1e8cec496a0897e62268c6f08f2919413e75c1)
Tedy pro daný rekurentní vztah T(n) je v Θ(n³).
(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je
, za předpokladu
.)
Pokud platí:
![{\displaystyle \exists k\geq 0,f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4df3a24deef9a13632daad112340f2323383d9)
tak:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd9cc7ea2afe218dd55acae03c243c5691f0d1d9)
Z výše uvedené rovnice vidíme, že hodnoty jsou:
,
,
,
, ![{\displaystyle \log _{b}a=\log _{2}2=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdff057adab25703125287a7ac92a1dfcff256e6)
Nyní ověříme, že následující rovnost platí (v tomto případě k=0):
![{\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48040c594711b6633b957677fac1f65f1471b3eb)
Po dosazení dostaneme:
![{\displaystyle 10n=\Theta \left(n^{1}\right)=\Theta \left(n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb460e7d8e86fea95cd7d28cc212e25af9f7d7a1)
Protože rovnost platí, druhý případ master theoremu lze aplikovat, čímž dostáváme:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log n\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0bc0a78e787349f58656876ed96a7528cf1772b)
Po dosazení:
![{\displaystyle T(n)=\Theta \left(n\log n\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd9f5f5adca6f87c3bd2e17f42d097bb3404500)
Tedy pro daný rekurentní vztah T(n) je v Θ(n log n).
(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je
, za předpokladu
.)
Pokud platí:
pro nějaké ![{\displaystyle \epsilon >0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71)
a také platí:
pro nějaké
a dostatečně velké n
tak:
![{\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed2605cfa2632ffce5e3d5d7a5f2415a5e91222)
![{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62fcfb5a3e72ed578b3fd4de2618c01232fecc62)
Z výše uvedené rovnice vidíme, že hodnoty jsou:
,
,
, ![{\displaystyle \log _{b}a=\log _{2}2=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdff057adab25703125287a7ac92a1dfcff256e6)
Nyní ověříme, že následující rovnost platí:
![{\displaystyle f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac11e50bf598ac053919818f2158fc07e141f60a)
Pokud dosadíme hodnoty a zvolíme
= 1, dostaneme:
![{\displaystyle n^{2}=\Omega \left(n^{1+1}\right)=\Omega \left(n^{2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/110a31a52bdde8286204153828d11d7695c19b96)
Protože rovnost platí, ověříme druhou podmínku, konkrétně, že:
![{\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90e16559ef4aac0ab33033fd25bf0a5a50d21a0a)
Opět dosadíme hodnoty:
![{\displaystyle 2\left({\frac {n}{2}}\right)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd367f1b0d73e9745ef186a16e84a21a6e38a016)
![{\displaystyle \leq cn^{2}\Leftrightarrow {\frac {1}{2}}n^{2}\leq cn^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6a6f5ada3e3287dcef91e17c88cfeb703cdc22d)
Pokud zvolíme
, tak platí:
![{\displaystyle \forall n\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1962466af2a948799388e62bdbf6b684b366306b)
Tedy:
![{\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed2605cfa2632ffce5e3d5d7a5f2415a5e91222)
Opět dosadíme hodnoty a dostaneme:
![{\displaystyle T\left(n\right)=\Theta \left(n^{2}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39a8991cfc2cf54a91a010eed6620d56b256da41)
Tedy pro daný rekurentní vztah T(n) je v Θ(n²), což odpovídá f (n) v původním vzorci.
(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je
, za předpokladu
.)
Následující rovnice nelze vyřešit pomocí master theoremu:[1]
![{\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f57f2a9f50b9144e6b007820d9367629e249cbbc)
To protože a (2n) není konstanta.
![{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0087168fc93c6226a43c43e5a6efe4574c6992bc)
Mezi f(n) a
je nepolynomiální rozdíl.
![{\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+{\frac {1}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d35ad303d385f98b948468fd20ea0b30f40943c7)
Nelze mít méně, než jeden podproblém (a<1).
![{\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20cbfdcb2830f150cd5bdf2bed2b34fe5a0d2aec)
f(n) není kladné.
![{\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03b8b924238e559f88461105a2524086762a7ce5)
Případ 3, ale porušení regularity.
V tomto článku byl použit překlad textu z článku Master theorem na anglické Wikipedii.
- ↑ Archivovaná kopie. www.cag.lcs.mit.edu [online]. [cit. 2009-04-24]. Dostupné v archivu pořízeném dne 2009-02-05.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sekce 4.3 (The master method) a 4.4 (Proof of the master theorem), pp.73–90.
- Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. Master theorem (včetně verze případu 2 zde zmíněné, která je silnější než ta z CLRS) je na pp. 268–270.