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

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

Вступ

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

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


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


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

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

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

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

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

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

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$, де $a\ge 1\text{, }b>1$

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

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

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

Випадок 1

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

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

$T(n)=\mathrm{\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-ϵ}\right)$

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

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

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

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

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

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

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

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

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

Випадок 2

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

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

$T(n)=\mathrm{\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$

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

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

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

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

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

$T(n)=\mathrm{\Theta }(n\log n)$

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

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

Випадок 3

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

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

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

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

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

$T\left(n\right)=\mathrm{\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)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$

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

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

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

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

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

$2{\left(\frac{n}{2}\right)}^2$$\le c{n}^2\iff \frac{1}{2}{n}^2\le c{n}^2$

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

$\frac{1}{2}{n}^2\le \frac{1}{2}{n}^2,$ $\mathrm{\forall }n\ge 1$

Отже далі:

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

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

$T\left(n\right)=\mathrm{\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-ϵ})$ якщо $0<ϵ\le {\log }_{3}12-2.$ Отже, по першому випадку майстер-методу, ми маємо $S(m)=\mathrm{\Theta }(m^{{\log }_{3}12}).$ Замінюючи змінні назад до початкового рекурентного співвідношення виводимо:

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

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

$T(n)=\mathrm{\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^{lo{g}_{2}2}}=\frac{n}{n\log n}=\frac{1}{\log n}$. Видно, що $\frac{1}{\log n}<n^{ϵ}$ для будь-якої сталої $ϵ>0$. Тому, різниця не поліноміальна і не можна застосувати майстер-метод.

Доведення

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

$T(n)=\{\begin{array}{cc}O(n^{{\log }_{b}a}),& \text{if }a>b^d\\ O(n^d\log n),& \text{if }a=b^d\\ O(n^d),& \text{if }a<b^d\end{array}$

В цьому доведенні ми покладемо $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\iff a=b^d\iff {\log }_{b}a=d{\log }_{b}b\iff {\log }_{b}a=d.$

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

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

Шаблон:EquationNote $=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.$

Шаблон:EquationNote $=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).$

Шаблон:EquationNote $=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$