Анализ рекуррентных соотношений. Мастер-теорема
Перейти к навигации
Перейти к поиску
Пусть решается задача размера 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).
Ссылки
Теория: