Русская Википедия:Основная теорема о рекуррентных соотношениях
Основная теорема о рекуррентных соотношениях используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй», например, при оценке времени их выполнения. Теорема была введена и доказана Джоном Бентли, Доротеном Хакеном и Джеймсом Хакеном в 1980 году. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была приведена.
Не все рекурсивные соотношения могут быть решены с помощью основной теоремы. Существует несколько её обобщений, в том числе Шаблон:Iw.
Описание
Рассмотрим задачу, которую можно решить рекурсивным алгоритмом:
function T(input n: размер задачи): if n < некоторая константа k: решить задачу относительно n нерекурсивно else: определить множество из a подзадач, каждая размера n/b вызвать функцию T рекурсивно для каждой подзадачи объединить решения end
В приведённом примере алгоритм рекурсивно разделяет исходную задачу размера n на несколько новых подзадач, каждая размером n/b. Такое разбиение может быть представлено в виде дерева вызовов, в котором каждый узел соответствует рекурсивному вызову, а ветви, исходящие из узла — последующим вызовам для подзадач. Каждый узел будет иметь a ветвей. Также в каждом узле производится объём работы, соответствующий размеру текущей подзадачи n (переданному в данный вызов функции) согласно соотношению <math>f(n)</math>. Общий объём работы алгоритма определяется как сумма всех работ в узлах данного дерева.
Вычислительная сложность подобных алгоритмов может быть представлена в виде рекуррентного соотношения <math>T(n) = a \, T\left(\frac{n}{b}\right) + f(n)</math>. Его можно решить путём многократных подстановок выражения <math>T\left(\frac{n}{b}\right)</math>.[1]
С помощью основной теоремы возможно быстрое вычисление подобных соотношений, что позволяет получить асимптотическую оценку времени работы рекурсивных алгоритмов в нотации O(n) (Θ-нотации), не производя подстановок.
Общая форма
Основная теорема рассматривает следующие рекуррентные соотношения:
- <math>T(n) = a \, T\left(\frac{n}{b}\right) + f(n), \quad \text{где}~ a \geqslant 1,\ b > 1.</math>
В применении к анализу алгоритмов константы и функции обозначают:
- n — размер задачи.
- a — количество подзадач в рекурсии.
- n/b — размер каждой подзадачи. (Предполагается, что все подзадачи на каждом этапе имеют одинаковый размер.)
- f (n) — оценка сложности работы, производимой алгоритмом вне рекурсивных вызовов. В неё также включается вычислительная стоимость деления на подзадачи и объединения результатов решения подзадач.
Основная теорема позволяет получить асимптотическую оценку для следующих трёх случаев:
Вариант 1
Общая форма
Если <math>f(n) = O(n^c)</math>, и выполняется соотношение <math>c < \log_b a</math>, тогда:
- <math>T(n) = \Theta\left( n^{\log_b a} \right).</math>
Пример
- <math>T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2.</math>
Согласно формуле, значения констант и сложности нерекурсивной части задачи:
- <math>a = 8,\ b = 2,\ f(n) = 1000n^2,</math>
- <math>f(n) = O(n^c)</math>, где <math>c = 2</math>.
Затем проверяем, выполняется ли соотношение 1-го варианта:
- <math>\log_b a = \log_2 8 = 3 > c</math>.
Следовательно,
- <math>T(n) = \Theta\left( n^{\log_b a} \right) = \Theta(n^3).</math>
(Для данного примера точное решение рекуррентности даёт <math>T(n) = 1001 n^3 - 1000 n^2</math>, при условии <math>T(1) = 1</math>.)
Вариант 2
Общая форма
Если для некоторой константы <math>k \geqslant 0</math> выполняется
- <math>f(n) = \Theta(n^c \log^k n)</math>, где <math>c = \log_b a</math>.
Тогда
- <math>T(n) = \Theta(n^c \log^{k+1} n).</math>
Пример
<math>T(n) = 2 T\left(\frac{n}{2}\right) + 10n.</math>
Согласно формуле, значения констант и сложности не рекурсивной части задачи:
- <math>a = 2,\ b = 2,\ c = 1,\ f(n) = 10n,</math>
- <math>f(n) = \Theta(n^c \log^k n)</math>, где <math>c = 1,\ k = 0</math>.
Проверяем соотношение варианта 2:
- <math>\log_b a = \log_2 2 = 1</math>, и следовательно, <math>c = \log_b a</math>.
В соответствии с 2-м вариантом основной теоремы,
- <math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta(n^1 \log^1 n) = \Theta(n \log n).</math>
Таким образом, рекуррентное соотношение T(n) равно Θ(n log n).
(Этот результат может быть проверен точным решением соотношения, в котором <math>T(n) = n + 10 n\log_2 n</math>, при условии <math>T(1) = 1</math>.)
Вариант 3
Общая форма
Если выполняется
- <math>f(n) = \Omega(n^c)</math>, где <math>c > \log_b a</math>,
а также верно, что
- <math>a f\left( \frac{n}{b} \right) \leqslant k f(n)</math> для некоторой константы <math>k < 1</math> и достаточно больших <math>n</math> (так называемое условие регулярности), тогда
- <math>T(n) = \Theta\big(f(n)\big).</math>
Пример
- <math>T(n) = 2 T\left(\frac{n}{2}\right) + n^2.</math>
Значения констант и функции:
- <math>a = 2,\ b = 2,\ f(n) = n^2,</math>
- <math>f(n) = \Omega(n^c)</math>, где <math>c = 2</math>.
Проверяем, что выполняется соотношение из варианта 3:
- <math>\log_b a = \log_2 2 = 1</math>, и, следовательно, <math>c > \log_b a</math>.
Также выполняется условие регулярности:
- <math> 2 \left(\frac{n^2}{4}\right) \leqslant k n^2 </math> при выборе <math>k = 1/2</math>.
Следовательно, согласно 3-му варианту основной теоремы,
- <math>T(n) = \Theta\big(f(n)\big) = \Theta(n^2).</math>
Данное рекуррентное соотношение T(n) равно Θ(n2), что совпадает с f(n) в изначальной формуле.
(Этот результат подтверждается точным решением рекуррентности, в котором <math>T(n) = 2 n^2 - n</math>, при условии <math>T(1) = 1</math>.)
Выражения, не решаемые основной теоремой
Следующие соотношения не могут быть решены с применением основной теоремы:[2]
- <math>T(n) = 2^n T\left(\frac{n}{2}\right) + n^n.</math>
- a не является константой, для основной теоремы требуется постоянное количество подзадач.
- <math>T(n) = 2 T\left(\frac{n}{2}\right) + \frac{n}{\log n}.</math>
- Между f(n) и <math>n^{\log_b a}</math> существует неполиномиальная зависимость.
- <math>T(n) = 0{,}5 T\left(\frac{n}{2}\right) + n.</math>
- a < 1, но основная теорема требует наличия хотя бы одной подзадачи.
- <math>T(n) = 64 T\left(\frac{n}{8}\right) - n^2 \log n.</math>
- f(n) является отрицательной величиной.
- <math>T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos n).</math>
- Близко к варианту 3, но не выполняется условие регулярности.
Во втором примере разница между <math>f(n)</math> и <math>n^{\log_b a}</math> может быть выражена соотношением <math>\frac{f(n)}{n^{\log_b a}} = \frac{\frac{n}{\log n}}{n^{\log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n}.</math> Из него видно, что <math>\frac{1}{\log n} < n^\varepsilon</math> для любой константы <math>\varepsilon > 0</math>. Следовательно, разница не является полиномом, и основная теорема неприменима.
Применение к некоторым алгоритмам
Алгоритм | Рекуррентное соотношение | Время работы | Примечание |
---|---|---|---|
Двоичный поиск | <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math> | <math>O(\log n)</math> | Основная теорема, 2 вариант: <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0, k = 0</math>[3] |
Обход двоичного дерева | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math> | <math>O(n)</math> | Основная теорема, 1 вариант: <math>c < \log_b a</math> где <math>a = 2, b = 2, c = 0</math>[3] |
Алгоритм Штрассена | <math>T(n) = 7 T\left(\frac{n}{2}\right) + O(n^2)</math> | <math>O(n^{\log_2 7}) \approx O(n^{2{,}81})</math> | Основная теорема, 1 вариант: <math>c < \log_b a</math>, где <math>a = 7, b = 2, c = 2</math>[4] |
Шаблон:Lang-en2 | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)</math> | <math>O(n)</math> | Теорема Akra — Bazzi для <math>p=1</math> и <math>g(u)=\log(u)</math> для получения <math>\Theta(2n - \log n)</math> |
Сортировка слиянием | <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math> | <math>O(n \log n)</math> | Основная теорема, 2 вариант: <math>c = \log_b a</math>, где <math>a = 2, b = 2, c = 1, k = 0</math> |
См. также
Примечания
Литература
- Шаблон:Книга Главы 4.3 (основная теорема) и 4.4 (доказательство)
- Шаблон:Книга Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73-90.Шаблон:Ref-en
- Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268—270.Шаблон:Ref-en
- CHAPTER 5. RECURSION AND RECURRENCES 5.2 The Master Theorem Шаблон:Wayback, CS 21/Math 19 — Course Notes Шаблон:Wayback, Ken Bogart and Cliff Stein: Discrete Math in Computer Science.
- ↑ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations". Шаблон:Wayback.
- ↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions"Шаблон:Недоступная ссылка.
- ↑ 3,0 3,1 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Шаблон:Wayback
- ↑ Шаблон:Cite web