Перейти до вмісту

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Вступ

[ред. | ред. код]

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

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

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

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

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

Алгоритми подібні до попереднього можна представити як рекурентне співвідношення . Ц е співвідношення можна успішно розгорнути для отримання виразу загального обсягу роботи.[1]

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

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

[ред. | ред. код]

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

, де

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

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

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

Випадок 1

[ред. | ред. код]

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

[ред. | ред. код]

Якщо для деякої сталої тоді:

Приклад

[ред. | ред. код]

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

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

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

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

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

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

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить , якщо взяти )

Випадок 2

[ред. | ред. код]

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

[ред. | ред. код]

Якщо для деякої сталої k ≥ 0 виконується, що , тоді:

Приклад

[ред. | ред. код]

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

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

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

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

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

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

(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить , якщо покласти )

Випадок 3

[ред. | ред. код]

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

[ред. | ред. код]

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

для деякої сталої

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

для деякої сталої і достатньо велиих тоді:

Приклад

[ред. | ред. код]

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

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

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

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

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

Якщо ми оберемо , тоді істинно:

Отже далі:

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

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

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

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

[ред. | ред. код]

Розглянемо

Нехай (тобто, нехай ). Тоді заміною змінних отримуємо:

Перейменовуючи маємо:

З випливає що якщо Отже, по першому випадку майстер-методу, ми маємо Замінюючи змінні назад до початкового рекурентного співвідношення виводимо:

Використовуючи тотожність можемо альтернативно записати як:

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

[ред. | ред. код]

Зауваження: три випадки не покривають усіх можливостей для Існує розрив між 1 і 2 коли менша від але не поліноміально менша. Подібний розрив присутній між 2 і 3 коли більша ніж але не поліноміально більша. Коли функція потрапляє а один з цих розривів або умова регулярності не дотримана у випадку 3, майстер-метод використовувати не можна.

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

  • a не стала, кількість підзадач мусить бути фіксованою
  • не поліноміальна різниця між f(n) і (дивись нижче)
  • a<1 не можна мати менш ніж одну підзадачу
  • f(n) не додатне
  • випадок 3, але порушена постійність.

В другому недопустимому прикладі, різницю між і можна виразити як співвідношення . Видно, що для будь-якої сталої . Тому, різниця не поліноміальна і не можна застосувати майстер-метод.

Доведення

[ред. | ред. код]

У разі коли можливо визначити щільну асимптотичну межу[3] в таких трьох випадках:

В цьому доведенні ми покладемо .

Дерево рекурсії матиме рівнів. На кожному рівні кількість підзадач збільшуватиметься в раз, отже на рівні матимемо підзадач. Кожна підзадача на рівні має розмір . Підзадача розміру потребує додаткової роботи і через те, що на рівні всього

З нашої формули для рівня ми бачимо, що робота зменшується, залишається незмінною або збільшується відповідно до . Три випадки залежать від того чи дорівнює 1, менша або більша від 1. Тепер зауважимо, що

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

 

 

 

 

(*)

У випадку, коли маємо

* 

Розглянемо випадок, коли . Тут нам знадобиться формула суми геометричного ряду:

де Довести можна за індукцією.

Якщо , тоді — стала, не залежить від

* 

Якщо , тоді

* 

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

.

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

[ред. | ред. код]
Алгоритм Рекурентне співвідношення Час виконання Коментар
Двійковий пошук Майстер-метод, випадок 2, де
Двійковий обхід дерева Майстер-метод, випадок 1, де
Сортування злиттям Майстер-метод, випадок 2, де

Примітки

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