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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Пусть решается задача размера 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).

Ссылки

Теория: