Майстер-метод

Майстер-метод (англ. master theorem, master method) надає готові розв'язки в асимптотичному записі (через використання нотації великого О) для рекурентних співвідношень які використовуються при аналізі алгоритмів «розділяй і володарюй». Його популяризувала канонічна книга з алгоритмів — Вступ в алгоритми, написана Томасом Корменом, Чарльзом Лейзерсоном, Рівестом і , в якій метод описано і доведено. Однак, не всі рекурентні співвідношення можна розв’язати за допомогою цього методу; узагальнює майстер-метод.

Вступ

Розглянемо проблему, яку можна розв'язати за допомогою як-от такого:

 підпрограма T( n : розмір проблеми ) визначений як: якщо n < 1 тоді вихід

 Виконати роботу обсягом f(n)

 T(n/b) T(n/b) ...повторити загалом a раз... T(n/b) кінець підпрограми 

В попередньому алгоритмі ми розділили задачу на кілька підзадач рекурсивно, кожна з підзадач розміром n/b. Це можна зобразити як дерево викликів, де кожна вершина дерева це один рекурсивний виклик, а її дочірні вершини є примірниками наступних викликів. В попередньому прикладі, кожна вершина матиме a дочірніх вершин. Кожна вершина виконує обсяг роботи відповідний до розміру отриманої підзадачі — n, який вимірюється як ${\displaystyle f(n)}$. Загальний обсяг роботи виконаної цілим деревом становить суму роботи, яку виконали усі вершини дерева.

Алгоритми подібні до попереднього можна представити як рекурентне співвідношення ${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$. Ц е співвідношення можна успішно розгорнути для отримання виразу загального обсягу роботи.

Майстер-метод дозволяє легко обчислити час виконання такого рекурсивного алгоритму в Θ-записі без розгортання рекурентного співвідношення.

Загальна форма

Майстер-метод розглядає рекурентні співвідношення такого виду:

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)\;}$, де ${\displaystyle \;a\geq 1{\mbox{, }}b>1}$

При застосуванні в розгляді рекурсивних алгоритмів, сталі і функції означають наступне:

• n — розмір задачі.
• a — кількість підзадач на кожному поступі рекурсії.
• n/b — розмір кожної з підпроблем. (Тут мається на увазі, що всі підзадачі однакового розміру.)
• f (n) — обсяг роботи поза рекурсивними викликами, який включає обсяг задачі розділення й обсяг злиття розв'язків підпроблем.

Опишемо три випадки докладніше.

Випадок 1

Загальний вид

Якщо ${\displaystyle f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right)}$ для деякої сталої ${\displaystyle \epsilon >0,}$ тоді:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}$

Приклад

${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}$

Як читач може побачити в попередній формулі, змінні мають такі значення:

${\displaystyle a=8,\,b=2,\,f(n)=1000n^{2},\,\log _{b}a=\log _{2}8=3}$

Тепер ми повинні перевірити, що мають місце наступні рівняння:

${\displaystyle f(n)=O\left(n^{\log _{b}a-\epsilon }\right)}$

${\displaystyle 1000n^{2}=O\left(n^{3-\epsilon }\right)}$

Якщо ми оберемо ${\displaystyle \epsilon }$ = 1, ми отримуємо:

${\displaystyle 1000n^{2}=O\left(n^{3-1}\right)=O\left(n^{2}\right)}$

Раз рівняння виконується, перший випадок майстер-метода можна застосувати для цього рекурентного співвідношення, отже отримуємо:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}$

Якщо підставити значення, зрештою отримуємо:

${\displaystyle T(n)=\Theta \left(n^{3}\right)}$

Отже наше рекурентне співвідношення T(n) обмежене Θ(n³).

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$, якщо взяти ${\displaystyle T(1)=1.}$)

Випадок 2

Загальний вид

Якщо для деякої сталої k ≥ 0 виконується, що ${\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)}$, тоді:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)}$

Приклад

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n}$

Як читач може побачити в попередній формулі, змінні мають такі значення:

${\displaystyle a=2,\,b=2,\,k=0,\,f(n)=10n,\,\log _{b}a=\log _{2}2=1}$

Тепер ми повинні перевірити, що мають місце наступні рівняння (при k=0):

${\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\right)}$

Якщо підставити значення, ми отримаємо:

${\displaystyle 10n=\Theta \left(n^{1}\right)=\Theta \left(n\right)}$

Через те, що рівняння виконуються, тут можна застосувати другий випадок майстер-метода, отримуємо:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)}$

З підставковою значень отримуємо:

${\displaystyle T(n)=\Theta \left(n\log n\right)}$

Отже наше рекурентне співвідношення T(n) обмежене Θ(n log n).

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить ${\displaystyle T(n)=n+10n\log _{2}n}$, якщо покласти ${\displaystyle T(1)=1.}$)

Випадок 3

Загальний вигляд

Як що правда що:

${\displaystyle f(n)=\Omega \left(n^{\log _{b}(a)+\epsilon }\right)}$ для деякої сталої ${\displaystyle \epsilon >0}$

і якщо також істинно, що:

${\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}$ для деякої сталої ${\displaystyle c<1}$ і достатньо велиих ${\displaystyle n,}$ тоді:

${\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}$

Приклад

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}$

Як можна побачити в попередній формулі, змінні мають такі значення:

${\displaystyle a=2,\,b=2,\,f(n)=n^{2},\,\log _{b}a=\log _{2}2=1}$

Тепер ми повинні перевірити, що мають місце наступні рівняння:

${\displaystyle f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)}$

Якщо підставити значення і вибрати ${\displaystyle \epsilon }$ = 1, ми отримаємо:

${\displaystyle n^{2}=\Omega \left(n^{1+1}\right)=\Omega \left(n^{2}\right)}$

Через те, що це рівняння виконується, ми маємо перевірити другу умову, тобто, якщо істинно, що:

${\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}$

Якщо ми підставимо більше значень, ми отримаємо число:

${\displaystyle 2\left({\frac {n}{2}}\right)^{2}}$${\displaystyle \leq cn^{2}\Leftrightarrow {\frac {1}{2}}n^{2}\leq cn^{2}}$

Якщо ми оберемо ${\displaystyle c={\frac {1}{2}}}$, тоді істинно:

${\displaystyle {\frac {1}{2}}n^{2}\leq {\frac {1}{2}}n^{2},}$ ${\displaystyle \forall n\geq 1}$

Отже далі:

${\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right).}$

Продовжуючи підстановки, ми отримуємо:

${\displaystyle T\left(n\right)=\Theta \left(n^{2}\right).}$

Отже наше рекурентне співвідношення T(n) обмежене Θ(n²), що відповідає f (n) даної формули.

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить ${\displaystyle T(n)=2n^{2}-n}$, прийняв ${\displaystyle T(1)=1}$.)

Заміна змінних

Розглянемо ${\displaystyle T(n)=12T(n^{1/3})+\log(n)^{2}.}$

Нехай ${\displaystyle n=3^{m}}$ (тобто, нехай ${\displaystyle m=\log _{3}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}}$

Перейменовуючи ${\displaystyle S(m)=T(3^{m})}$ маємо: ${\displaystyle S(m)=12S(m/3)+(\log 3)^{2}m^{2}.}$

З ${\displaystyle \log _{3}{12}>\log _{3}{9}=2}$ випливає що ${\displaystyle (\log 3)^{2}m^{2}=O(n^{\log _{3}{12}-\epsilon })}$ якщо ${\displaystyle 0<\epsilon \leq \log _{3}{12}-2.}$ Отже, по першому випадку майстер-методу, ми маємо ${\displaystyle S(m)=\Theta (m^{\log _{3}{12}}).}$ Замінюючи змінні назад до початкового рекурентного співвідношення виводимо:

${\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}})}$

Використовуючи тотожність ${\displaystyle x^{\log _{b}{y}}=y^{\log _{b}{x}},}$ можемо альтернативно записати як:

${\displaystyle T(n)=\Theta (12^{\log _{3}{\log n}})}$

Недопустимі рівняння

Зауваження: три випадки не покривають усіх можливостей для ${\displaystyle f(n).}$ Існує розрив між 1 і 2 коли ${\displaystyle f(n)}$ менша від ${\displaystyle n^{\log {b^{a}}},}$ але не поліноміально менша. Подібний розрив присутній між 2 і 3 коли ${\displaystyle f(n)}$ більша ніж ${\displaystyle n^{\log {b^{a}}},}$ але не поліноміально більша. Коли функція ${\displaystyle f(n)}$ потрапляє а один з цих розривів або умова регулярності не дотримана у випадку 3, майстер-метод використовувати не можна.

Наступні рівняння не можливо розв'язати із використанням майстер-методу:

• ${\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}$

  a не стала, кількість підзадач мусить бути фіксованою

• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}$

  не поліноміальна різниця між f(n) і ${\displaystyle n^{\log _{b}a}}$ (дивись нижче)

• ${\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n}$

  a<1 не можна мати менш ніж одну підзадачу

• ${\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}$

  f(n) не додатне

• ${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}$

  випадок 3, але порушена постійність.

В другому недопустимому прикладі, різницю між ${\displaystyle f(n)}$ і ${\displaystyle n^{\log _{b}a}}$ можна виразити як співвідношення ${\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {\frac {n}{\log n}}{n^{log_{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}$. Видно, що ${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$ для будь-якої сталої ${\displaystyle \epsilon >0}$. Тому, різниця не поліноміальна і не можна застосувати майстер-метод.

Доведення

У разі коли ${\displaystyle f(n)=n^{d}}$ можливо визначити щільну асимптотичну межу в таких трьох випадках:

${\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}}}$

В цьому доведенні ми покладемо ${\displaystyle T(1)=1}$.

Дерево рекурсії матиме ${\displaystyle \log _{b}n}$ рівнів. На кожному рівні кількість підзадач збільшуватиметься в ${\displaystyle a}$ раз, отже на рівні ${\displaystyle i}$ матимемо ${\displaystyle a^{i}}$ підзадач. Кожна підзадача на рівні ${\displaystyle i}$ має розмір ${\displaystyle n/b^{i}}$. Підзадача розміру ${\displaystyle n/b^{i}}$ потребує ${\displaystyle (n/b^{i})^{d}}$ додаткової роботи і через те, що на рівні ${\displaystyle i}$ всього

${\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}.}$

З нашої формули для рівня ${\displaystyle i}$ ми бачимо, що робота зменшується, залишається незмінною або збільшується відповідно до ${\displaystyle \left({\frac {a}{b^{d}}}\right)^{i}}$. Три випадки залежать від того чи ${\displaystyle \left({\frac {a}{b^{d}}}\right)^{i}}$ дорівнює 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.}$

Отже видно звідки з'явились три випадки. Загалом, ми маємо такий обсяг роботи

${\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}}$

(*)

У випадку, коли ${\displaystyle a=b^{d}}$ маємо

* ${\displaystyle =n^{d}(\log _{b}n+1)=O(n^{d}\log _{b}n)}$

Розглянемо випадок, коли ${\displaystyle a<b^{d}}$. Тут нам знадобиться формула суми геометричного ряду:

${\displaystyle \sum _{i=0}^{k}r^{i}={\frac {r^{k+1}-1}{r^{k}-1}},}$ де ${\displaystyle r<1.}$ Довести можна за індукцією.

Якщо ${\displaystyle r<1}$, тоді ${\displaystyle {\frac {r^{k+1}-1}{r^{k}-1}}<{\frac {1}{1-r}}=c_{1}}$ — стала, не залежить від ${\displaystyle k.}$

* ${\displaystyle =c_{1}n^{d}=O(n^{d})}$

Якщо ${\displaystyle r>1}$, тоді ${\displaystyle {\frac {r^{k+1}-1}{r^{k}-1}}<{\frac {r^{k+1}}{1-r}}=r^{k}{\frac {r}{r-1}}=O(r^{k}).}$

* ${\displaystyle =O(n^{d}\left({\frac {a}{b^{d}}}\right)^{\log _{b}n}).}$

Розглянемо внутрішній вираз:

${\displaystyle n^{d}\left({\frac {a}{b^{d}}}\right)^{\log _{b}n}=n^{d}{\frac {a^{\log _{b}n}}{b^{d\log _{b}n}}}=n^{d}{\frac {a^{\log _{b}n}}{n^{d}}}=a^{\log _{b}n}=n^{\log _{b}a}}$.

Застосування до поширених алгоритмів

Алгоритм	Рекурентне співвідношення	Час виконання	Коментар
Двійковий пошук	${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+O(1)}$	${\displaystyle O(\log n)}$	Майстер-метод, випадок 2, де ${\displaystyle a=1,b=2,\log _{b}a=0,k=0}$
Двійковий обхід дерева	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(1)}$	${\displaystyle O(n)}$	Майстер-метод, випадок 1, де ${\displaystyle a=2,b=2,\log _{b}a=0}$
Сортування злиттям	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$	${\displaystyle O(n\log n)}$	Майстер-метод, випадок 2, де ${\displaystyle a=2,b=2,\log _{b}a=1,k=0}$

Примітки

1. Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html [ 22 червня 2012 у Wayback Machine.]
2. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf^{[недоступне посилання з квітня 2019]}
3. В програмуванні часто замість ${\displaystyle \Theta }$ для вказання функції, що обмежує досліджувану функцію згори і знизу, використовують ${\displaystyle O}$.