Майстер-метод (англ. 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, ми отримуємо:
Раз рівняння виконується, перший випадок майстер-метода можна застосувати для цього рекурентного співвідношення, отже отримуємо:
Якщо підставити значення, зрештою отримуємо:
Отже наше рекурентне співвідношення T(n) обмежене Θ(n3).
(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить , якщо взяти )
Якщо для деякої сталої k ≥ 0 виконується, що , тоді:
Як читач може побачити в попередній формулі, змінні мають такі значення:
Тепер ми повинні перевірити, що мають місце наступні рівняння (при k=0):
Якщо підставити значення, ми отримаємо:
Через те, що рівняння виконуються, тут можна застосувати другий випадок майстер-метода, отримуємо:
З підставковою значень отримуємо:
Отже наше рекурентне співвідношення T(n) обмежене Θ(n log n).
(Цей вислід підтверджується точним розв'язком рекурентного співвідношення, який становить , якщо покласти )
Як що правда що:
- для деякої сталої
і якщо також істинно, що:
- для деякої сталої і достатньо велиих тоді:
Як можна побачити в попередній формулі, змінні мають такі значення:
Тепер ми повинні перевірити, що мають місце наступні рівняння:
Якщо підставити значення і вибрати = 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, де
|