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

Майстер-метод (англ. 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)$ . Ц е співвідношення можна успішно розгорнути для отримання виразу загального обсягу роботи.^[1]

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

Загальна форма ред.

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

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, майстер-метод використовувати не можна.

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

$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}$ можливо визначити щільну асимптотичну межу^[3] в таких трьох випадках:

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$

Примітки ред.

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

[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] В програмуванні часто замість $\Theta$ для вказання функції, що обмежує досліджувану функцію згори і знизу, використовують $O$ .

[1]

[2]

[3]