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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Майстер-метод (англ. 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) = 8 T\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) обмежене Θ(n3).

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить T(n) = 1001 n^3 - 1000 n^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) = 2 T\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 + 10 n\log_2 n, якщо покласти T(1) = 1.)

Випадок 3[ред.ред. код]

Загальний вигляд[ред.ред. код]

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

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

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

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

Приклад[ред.ред. код]

T(n) = 2 T\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)

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

a f\left( \frac{n}{b} \right) \le c f(n)

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

2 \left( \frac{n}{2} \right)^2 \le c n^2 \Leftrightarrow \frac{1}{2} n^2 \le cn^2

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

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

Отже далі:

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

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

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

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

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

Заміна змінних[ред.ред. код]

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

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

T(3^m) = 12T((3^m)^{1/3}) + (\log(3^m))^{2} = 12T(3^{m/3}) + (m\log3)^{2} = 12T(3^{m/3}) + (\log3)^{2}m^2

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

З \log_3{12}>\log_3{9}=2 випливає що (\log3)^{2}m^2=O(n^{\log_3{12}-\epsilon}) якщо 0<\epsilon\le\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_3n)^{\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^nT\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) = 2 T\left(\frac{n}{2}\right) + O(1) O(n) Майстер-метод, випадок 1, де a = 2, b = 2, \log_b a = 0
Сортування злиттям T(n) = 2 T\left(\frac{n}{2}\right) + O(n) O(n \log n) Майстер-метод, випадок 2, де 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
  2. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf
  3. В програмуванні часто замість \Theta для вказання функції, що обмежує досліджувану функцію згори і знизу, використовують O.