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

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

Вступ

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

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


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


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

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

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

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

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

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

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

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

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

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

Випадок 1

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

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Випадок 2

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

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

$T(n)=\Theta \left(n\log n\right)$

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

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

Випадок 3

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

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

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

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

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

$T\left(n\right)=\Theta \left(f\left(n\right)\right)$

Приклад

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

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

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

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

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

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

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

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

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

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

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

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

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

Отже далі:

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

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

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

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

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

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

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

Нехай $n=3^{m}$ (тобто, нехай $m=\log _{3}n$). Тоді заміною змінних отримуємо:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доведення

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

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

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

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

$a^{i}(n/b^{i})^{d}=n^{d}\left({\frac {a^{i}}{b^{di}}}\right)=n^{d}\left({\frac {a}{b^{d}}}\right)^{i}.$

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

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

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

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

(*)

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

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

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

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

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

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

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

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

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

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

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

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