Master theorem (для допитливих)¶

Додатковий матеріал

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

Постановка задачі¶

Багато рекурсивних алгоритмів мають складність виду:

\[T(n) = a \cdot T\!\left(\frac{n}{b}\right) + O(n^c)\]

де:

\(a\) — кількість рекурсивних викликів
\(b\) — у скільки разів зменшується розмір задачі
\(O(n^c)\) — робота, що виконується поза рекурсією (розбиття + об'єднання)

Master theorem дає відповідь одразу, без побудови дерева рекурсії.

Формулювання¶

Нехай \(T(n) = a \cdot T(n/b) + O(n^c)\), де \(a \geq 1\), \(b > 1\), \(c \geq 0\).

Визначимо критичний показник: \(\log_b a\).

Тоді:

Випадок	Умова	Результат
Випадок 1	\(c < \log_b a\)	\(T(n) = O(n^{\log_b a})\)
Випадок 2	\(c = \log_b a\)	\(T(n) = O(n^c \log n)\)
Випадок 3	\(c > \log_b a\)	\(T(n) = O(n^c)\)

Інтуїція¶

Випадок 1: рекурсивні виклики домінують — дерево рекурсії "широке", основна робота на листках
Випадок 2: робота розподілена рівномірно по рівнях — кожен рівень дає \(O(n^c)\) роботи, рівнів \(\log_b n\)
Випадок 3: робота на верхньому рівні домінує — рекурсивні виклики не додають суттєвої роботи

Приклади¶

Приклад 1: Бінарний пошук¶

\[T(n) = 1 \cdot T(n/2) + O(1)\]

Параметри: \(a = 1\), \(b = 2\), \(c = 0\).

\(\log_b a = \log_2 1 = 0 = c\) → Випадок 2.

\[T(n) = O(n^0 \log n) = O(\log n)\]

Приклад 2: Merge sort¶

\[T(n) = 2 \cdot T(n/2) + O(n)\]

Параметри: \(a = 2\), \(b = 2\), \(c = 1\).

\(\log_b a = \log_2 2 = 1 = c\) → Випадок 2.

\[T(n) = O(n^1 \log n) = O(n \log n)\]

Приклад 3: Алгоритм Карацуби (множення великих чисел)¶

\[T(n) = 3 \cdot T(n/2) + O(n)\]

Параметри: \(a = 3\), \(b = 2\), \(c = 1\).

\(\log_b a = \log_2 3 \approx 1.585 > 1 = c\) → Випадок 1.

\[T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})\]

Приклад 4: Гіпотетичний алгоритм¶

\[T(n) = 2 \cdot T(n/2) + O(n^2)\]

Параметри: \(a = 2\), \(b = 2\), \(c = 2\).

\(\log_b a = \log_2 2 = 1 < 2 = c\) → Випадок 3.

\[T(n) = O(n^2)\]

Зведена таблиця відомих алгоритмів¶

Алгоритм	Рекурентність	\(a\)	\(b\)	\(c\)	\(\log_b a\)	Випадок	\(T(n)\)
Бінарний пошук	\(T(n/2) + O(1)\)	1	2	0	0	2	\(O(\log n)\)
Merge sort	\(2T(n/2) + O(n)\)	2	2	1	1	2	\(O(n \log n)\)
Quicksort (середній)	\(2T(n/2) + O(n)\)	2	2	1	1	2	\(O(n \log n)\)
Обхід дерева	\(2T(n/2) + O(1)\)	2	2	0	1	1	\(O(n)\)

Обмеження¶

Master theorem не застосовується, коли:

Рекурсивні виклики мають різний розмір (наприклад, \(T(n) = T(n/3) + T(2n/3) + O(n)\))
Розмір зменшується не в \(b\) разів, а на константу (наприклад, \(T(n) = T(n-1) + O(1)\))
Функція додаткової роботи не є поліноміальною

Для таких випадків використовують дерево рекурсії або метод підстановки.

Назад: Оцінка складності алгоритмів