Майстер-метод (англ. master theorem, master method) надає готові розв'язки в асимптотичному записі (через використання нотації великого О) для рекурентних співвідношень які використовуються при аналізі алгоритмів «розділяй і володарюй». Його популяризувала канонічна книга з алгоритмів — Вступ в алгоритми, написана Томасом Корменом, Чарльзом Лейзерсоном, Рівестом і Кліффордом Стейном, в якій метод описано і доведено. Однак, не всі рекурентні співвідношення можна розв’язати за допомогою цього методу; метод Акра-Баззі узагальнює майстер-метод.
Розглянемо проблему, яку можна розв'язати за допомогою рекурсивного алгоритму як-от такого:
підпрограма T( n : розмір проблеми ) визначений як:
якщо n < 1 тоді вихід
Виконати роботу обсягом f(n)
T(n/b)
T(n/b)
...повторити загалом a раз...
T(n/b)
кінець підпрограми
В попередньому алгоритмі ми розділили задачу на кілька підзадач рекурсивно, кожна з підзадач розміром n/b. Це можна зобразити як дерево викликів, де кожна вершина дерева це один рекурсивний виклик, а її дочірні вершини є примірниками наступних викликів. В попередньому прикладі, кожна вершина матиме a дочірніх вершин. Кожна вершина виконує обсяг роботи відповідний до розміру отриманої підзадачі — n, який вимірюється як
. Загальний обсяг роботи виконаної цілим деревом становить суму роботи, яку виконали усі вершини дерева.
Алгоритми подібні до попереднього можна представити як рекурентне співвідношення
. Ц е співвідношення можна успішно розгорнути для отримання виразу загального обсягу роботи.[1]
Майстер-метод дозволяє легко обчислити час виконання такого рекурсивного алгоритму в Θ-записі без розгортання рекурентного співвідношення.
Майстер-метод розглядає рекурентні співвідношення такого виду:
, де ![{\displaystyle \;a\geq 1{\mbox{, }}b>1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9424bb137348026f158e61d2ba84ddce05efa378)
При застосуванні в розгляді рекурсивних алгоритмів, сталі і функції означають наступне:
- n — розмір задачі.
- a — кількість підзадач на кожному поступі рекурсії.
- n/b — розмір кожної з підпроблем. (Тут мається на увазі, що всі підзадачі однакового розміру.)
- f (n) — обсяг роботи поза рекурсивними викликами, який включає обсяг задачі розділення й обсяг злиття розв'язків підпроблем.
Опишемо три випадки докладніше.
Якщо
для деякої сталої
тоді:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceb5444d7cb63715b7588d60e302cd6481723cf0)
![{\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d86a4deef09a035c732738b1888552d6a6c4e4f7)
Як читач може побачити в попередній формулі, змінні мають такі значення:
![{\displaystyle a=8,\,b=2,\,f(n)=1000n^{2},\,\log _{b}a=\log _{2}8=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f2ad2a8af3f060af88f3fb5ae72f454073a0d9f)
Тепер ми повинні перевірити, що мають місце наступні рівняння:
![{\displaystyle f(n)=O\left(n^{\log _{b}a-\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3827beaecd91ce195d76ae41440be08edc85721c)
![{\displaystyle 1000n^{2}=O\left(n^{3-\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dacf253c020a0d1571761e4cdb839610982e45bf)
Якщо ми оберемо
= 1, ми отримуємо:
![{\displaystyle 1000n^{2}=O\left(n^{3-1}\right)=O\left(n^{2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9bc7b6e2e195e80a996555658fd1665c00fc5b4)
Раз рівняння виконується, перший випадок майстер-метода можна застосувати для цього рекурентного співвідношення, отже отримуємо:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceb5444d7cb63715b7588d60e302cd6481723cf0)
Якщо підставити значення, зрештою отримуємо:
![{\displaystyle T(n)=\Theta \left(n^{3}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed05b3ea267fc7722736ba3e2d1ae0254971eb51)
Отже наше рекурентне співвідношення T(n) обмежене Θ(n3).
(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить
, якщо взяти
)
Якщо для деякої сталої k ≥ 0 виконується, що
, тоді:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/832781bbb8fbc32957079c4d36d72a8114a05b6a)
Як читач може побачити в попередній формулі, змінні мають такі значення:
![{\displaystyle a=2,\,b=2,\,k=0,\,f(n)=10n,\,\log _{b}a=\log _{2}2=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/055a8d9d9f8b35da252411c81f00aa3f646bd226)
Тепер ми повинні перевірити, що мають місце наступні рівняння (при k=0):
![{\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48040c594711b6633b957677fac1f65f1471b3eb)
Якщо підставити значення, ми отримаємо:
![{\displaystyle 10n=\Theta \left(n^{1}\right)=\Theta \left(n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb460e7d8e86fea95cd7d28cc212e25af9f7d7a1)
Через те, що рівняння виконуються, тут можна застосувати другий випадок майстер-метода, отримуємо:
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/832781bbb8fbc32957079c4d36d72a8114a05b6a)
З підставковою значень отримуємо:
![{\displaystyle T(n)=\Theta \left(n\log n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d1e10aca88e07dad16fcc1a15e4d0b2dc419391)
Отже наше рекурентне співвідношення T(n) обмежене Θ(n log n).
(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить
, якщо покласти
)
Як що правда що:
для деякої сталої ![{\displaystyle \epsilon >0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71)
і якщо також істинно, що:
для деякої сталої
і достатньо велиих
тоді:
![{\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed4853d676dfac75faed7777f19b695ee51f865b)
![{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62fcfb5a3e72ed578b3fd4de2618c01232fecc62)
Як можна побачити в попередній формулі, змінні мають такі значення:
![{\displaystyle a=2,\,b=2,\,f(n)=n^{2},\,\log _{b}a=\log _{2}2=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89ba3852e3a52da737f559acd65237b10db3567b)
Тепер ми повинні перевірити, що мають місце наступні рівняння:
![{\displaystyle f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac11e50bf598ac053919818f2158fc07e141f60a)
Якщо підставити значення і вибрати
= 1, ми отримаємо:
![{\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)
Через те, що це рівняння виконується, ми маємо перевірити другу умову, тобто, якщо істинно, що:
![{\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90e16559ef4aac0ab33033fd25bf0a5a50d21a0a)
Якщо ми підставимо більше значень, ми отримаємо число:
![{\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)
Якщо ми оберемо
, тоді істинно:
![{\displaystyle \forall n\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1962466af2a948799388e62bdbf6b684b366306b)
Отже далі:
![{\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\left(n\right)=\Theta \left(n^{2}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39a8991cfc2cf54a91a010eed6620d56b256da41)
Отже наше рекурентне співвідношення T(n) обмежене Θ(n2), що відповідає f (n) даної формули.
(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить
, прийняв
.)
Розглянемо
Нехай
(тобто, нехай
). Тоді заміною змінних отримуємо:
![{\displaystyle T(3^{m})=12T((3^{m})^{1/3})+(\log(3^{m}))^{2}=12T(3^{m/3})+(m\log 3)^{2}=12T(3^{m/3})+(\log 3)^{2}m^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80c0aba6434a9182a69702e225a26761800f2b74)
Перейменовуючи
маємо:
З
випливає що
якщо
Отже, по першому випадку майстер-методу, ми маємо
Замінюючи змінні назад до початкового рекурентного співвідношення виводимо:
![{\displaystyle T(n)=T(3^{m})=S(m)=\Theta (m^{\log _{3}{12}})=\Theta ((\log _{3}n)^{\log _{3}{12}})=\Theta ((\log n)^{\log _{3}{12}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/408a20349f8370e4cb51052fc3518cea63cf74d4)
Використовуючи тотожність
можемо альтернативно записати як:
![{\displaystyle T(n)=\Theta (12^{\log _{3}{\log n}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/967c96fa20dadbf9cbd0d3dafafde06aa26105a4)
Зауваження: три випадки не покривають усіх можливостей для
Існує розрив між 1 і 2 коли
менша від
але не поліноміально менша. Подібний розрив присутній між 2 і 3 коли
більша ніж
але не поліноміально більша. Коли функція
потрапляє а один з цих розривів або умова регулярності не дотримана у випадку 3, майстер-метод використовувати не можна.
Наступні рівняння не можливо розв'язати із використанням майстер-методу:[2]
- a не стала, кількість підзадач мусить бути фіксованою
- не поліноміальна різниця між f(n) і
(дивись нижче)
- a<1 не можна мати менш ніж одну підзадачу
- f(n) не додатне
- випадок 3, але порушена постійність.
В другому недопустимому прикладі, різницю між
і
можна виразити як співвідношення
. Видно, що
для будь-якої сталої
. Тому, різниця не поліноміальна і не можна застосувати майстер-метод.
У разі коли
можливо визначити щільну асимптотичну межу[3] в таких трьох випадках:
![{\displaystyle T(n)={\begin{cases}O(n^{\log _{b}a}),&{\mbox{if }}a>b^{d}\\O(n^{d}\log n),&{\mbox{if }}a=b^{d}\\O(n^{d}),&{\mbox{if }}a<b^{d}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d59d3e806f49950e0e5eb2cdcbf6506cceca471a)
В цьому доведенні ми покладемо
.
Дерево рекурсії матиме
рівнів. На кожному рівні кількість підзадач збільшуватиметься в
раз, отже на рівні
матимемо
підзадач. Кожна підзадача на рівні
має розмір
. Підзадача розміру
потребує
додаткової роботи і через те, що на рівні
всього
![{\displaystyle a^{i}(n/b^{i})^{d}=n^{d}\left({\frac {a^{i}}{b^{di}}}\right)=n^{d}\left({\frac {a}{b^{d}}}\right)^{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b555a3e7fff273601061db66da322ee3f7e28142)
З нашої формули для рівня
ми бачимо, що робота зменшується, залишається незмінною або збільшується відповідно до
. Три випадки залежать від того чи
дорівнює 1, менша або більша від 1. Тепер зауважимо, що
![{\displaystyle \left({\frac {a}{b^{d}}}\right)^{i}=1\Leftrightarrow a=b^{d}\Leftrightarrow \log _{b}a=d\log _{b}b\Leftrightarrow \log _{b}a=d.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4263f4e6e36b96ef1c9c0319da5f475c25ffab36)
Отже видно звідки з'явились три випадки. Загалом, ми маємо такий обсяг роботи
-
![{\displaystyle \sum _{i=0}^{\log _{b}n}n^{d}\left({\frac {a}{b^{d}}}\right)^{i}=n^{d}\sum _{i=0}^{\log _{b}n}\left({\frac {a}{b^{d}}}\right)^{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/962aa3c235a7188b8e539a55b43cfa0489c556bc)
|
|
(*)
|
У випадку, коли
маємо
- *
![{\displaystyle =n^{d}(\log _{b}n+1)=O(n^{d}\log _{b}n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/def367f1881c93ee83a5960600fed959f0b3f4fb)
Розглянемо випадок, коли
. Тут нам знадобиться формула суми геометричного ряду:
де
Довести можна за індукцією.
Якщо
, тоді
— стала, не залежить від
- *
![{\displaystyle =c_{1}n^{d}=O(n^{d})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b33ff2abfb641b2a78ad01910f9c1d264052da57)
Якщо
, тоді
- *
![{\displaystyle =O(n^{d}\left({\frac {a}{b^{d}}}\right)^{\log _{b}n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864f40fa5241a66d4fd6dacb3f2b255b7592e8bf)
Розглянемо внутрішній вираз:
.
Алгоритм
|
Рекурентне співвідношення
|
Час виконання
|
Коментар
|
Двійковий пошук
|
|
|
Майстер-метод, випадок 2, де
|
Двійковий обхід дерева
|
|
|
Майстер-метод, випадок 1, де
|
Сортування злиттям
|
|
|
Майстер-метод, випадок 2, де
|