Просмотр кода страницы Анализ рекуррентных соотношений. Мастер-теорема

Пусть решается задача размера ''N'', при этом рекурсивно обрабатываются ''a'' подзадач размера ''N / b'', а ответ восстанавливается из ответов на подзадачи за ''O(N<sup>c</sup>)'' операций.

Тогда:

* На нулевом уровне дерева рекурсии имеется одна задача размера ''N'', число операций равно ''N<sup>c</sup>'';
* На первом уровне дерева рекурсии имеются ''a'' подзадач размера ''N / b'', число операций равно ''a &times; (N / b)<sup>c</sup>'';
* На втором уровне дерева рекурсии имеются ''a<sup>2</sup>'' подзадач размера ''N / b<sup>2</sup>'', число операций равно ''a<sup>2</sup> &times; (N / b<sup>2</sup>)<sup>c</sup>'';
* ...
* На ''i''-м уровне дерева рекурсии имеются ''a<sup>i</sup>'' подзадач размера ''N / b<sup>i</sup>'', число операций равно ''a<sup>i</sup> &times; (N / b<sup>i</sup>)<sup>c</sup>'';
* ...
* На ''(log<sub>b</sub>N)''-м уровне дерева рекурсии имеются ''a<sup>(log<sub>b</sub>N)</sup>'' подзадач размера 1, число операций равно ''a<sup>(log<sub>b</sub>N)</sup>''.

Общее количество операций равно ''N<sup>c</sup> + a &times; (N / b)<sup>c</sup> + a<sup>2</sup> &times; (N / b<sup>2</sup>)<sup>c</sup> + ... + a<sup>(log<sub>b</sub>N)</sup>'', или '''''N<sup>c</sup> &times; (1 + a / b<sup>c</sup> + (a / b<sup>c</sup>)<sup>2</sup> + ... + (a / b<sup>c</sup>)<sup>log<sub>b</sub>N</sup>)'''''.

Тогда:

* '''Если ''a / b<sup>c</sup> < 1''''', то количество операций на каждом уровне рекурсии уменьшается, геометрическая прогрессия доминируется первым членом (''O(1)''), '''асимптотическая оценка решения равна O(N<sup>c</sup>)''''';
* '''Если ''a / b<sup>c</sup> = 1''''', то количество операций на каждом уровне рекурсии одинаково, асимптотическая оценка геометрической прогрессии линейная относительно числа членов (''O(log<sub>b</sub>N)''), '''асимптотическая оценка решения равна O(N<sup>c</sup>logN)''''';
* '''Если ''a / b<sup>c</sup> > 1''''', то количество операций на каждом уровне рекурсии увеличивается, геометрическая прогрессия доминируется последним членом (''O((a / b<sup>c</sup>)<sup>log<sub>b</sub>a</sup>''), '''асимптотическая оценка решения равна''' ''O(N<sup>c</sup> &times; (a / b<sup>c</sup>)<sup>log<sub>b</sub>N</sup>) = O(N<sup>c</sup> &times; (N<sup>log<sub>b</sub>a</sup> / N<sup>c</sup>)) = '''''O(N<sup>log<sub>b</sub>a</sup>)'''''.

Примеры:

* Двоичный поиск: ''T(N) = T(N / 2) + O(1); a = 1, b = 2, c = 0; a / b<sup>c</sup> = 1, T(N) = O(logN)'';
* Сортировка слиянием: ''T(N) = 2 &times; T(N / 2) + O(N); a = 2, b = 2, c = 1; a / b<sup>c</sup> = 1, T(N) = O(NlogN)'';
* Обход двоичного дерева: ''T(N) = 2 &times; T(N / 2) + O(1); a = 2, b = 2, c = 0; a / b<sup>c</sup> > 1; T(N) = O(N)'';
* Умножение чисел методом Карацубы: ''T(N) = 3 &times; T(N / 2) + O(1); a = 3, b = 2, c = 0; a / b<sup>c</sup> > 1; T(N) = O(N<sup>log<sub>2</sub>3</sup>)'';
* Умножение матриц методом Штрассена: ''T(N) = 7 &times; T(N / 2) + O(1); a = 7, b = 2, c = 0; a / b<sup>c</sup> > 1; T(N) = O(N<sup>log<sub>2</sub>7</sup>)''.

== Ссылки ==
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki &mdash; Мастер-теорема]
* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu &mdash; The Master Theorem]
* [http://brilliant.org/wiki/master-theorem/ brilliant.org — Master Theorem]
* [http://www.nayuki.io/page/master-theorem-solver-javascript nayuki.io &mdash; Master theorem solver]


[[Категория:Учебный курс «Алгоритмы и структуры данных»]]