Анализ рекуррентных соотношений. Мастер-теорема: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «Пусть решается задача размера ''N'', при этом рекурсивно обрабатываются ''a'' подзадач разме…»)
 
 
(не показаны 2 промежуточные версии этого же участника)
Строка 31: Строка 31:
* [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 — Мастер-теорема]
* [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 — Мастер-теорема]
* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]
* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]
* [http://brilliant.org/wiki/master-theorem/ brilliant.org — Master Theorem]
* [http://www.nayuki.io/page/master-theorem-solver-javascript nayuki.io — Master theorem solver]


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

Текущая версия от 17:06, 2 января 2020

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

Тогда:

  • На нулевом уровне дерева рекурсии имеется одна задача размера N, число операций равно Nc;
  • На первом уровне дерева рекурсии имеются a подзадач размера N / b, число операций равно a × (N / b)c;
  • На втором уровне дерева рекурсии имеются a2 подзадач размера N / b2, число операций равно a2 × (N / b2)c;
  • ...
  • На i-м уровне дерева рекурсии имеются ai подзадач размера N / bi, число операций равно ai × (N / bi)c;
  • ...
  • На (logbN)-м уровне дерева рекурсии имеются a(logbN) подзадач размера 1, число операций равно a(logbN).

Общее количество операций равно Nc + a × (N / b)c + a2 × (N / b2)c + ... + a(logbN), или Nc × (1 + a / bc + (a / bc)2 + ... + (a / bc)logbN).

Тогда:

  • Если a / bc < 1, то количество операций на каждом уровне рекурсии уменьшается, геометрическая прогрессия доминируется первым членом (O(1)), асимптотическая оценка решения равна O(Nc);
  • Если a / bc = 1, то количество операций на каждом уровне рекурсии одинаково, асимптотическая оценка геометрической прогрессии линейная относительно числа членов (O(logbN)), асимптотическая оценка решения равна O(NclogN);
  • Если a / bc > 1, то количество операций на каждом уровне рекурсии увеличивается, геометрическая прогрессия доминируется последним членом (O((a / bc)logba), асимптотическая оценка решения равна O(Nc × (a / bc)logbN) = O(Nc × (Nlogba / Nc)) = O(Nlogba).

Примеры:

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

Ссылки

Теория:

Источник — https://acm.khpnets.info/w39/index.php?title=Анализ_рекуррентных_соотношений._Мастер-теорема&oldid=2447