Основная теорема о рекуррентных соотношениях

Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была введена и доказана Джоном Бентли, Доротеном Хакеном и Джеймсом Хакеном в 1980 году. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была приведена.

Не все рекурсивные соотношения могут быть решены с помощью основной теоремы. Существует несколько её обобщений, в том числе Akra-Bazzi method.

Описание

Рассмотрим задачу, которую можно решить рекурсивным алгоритмом:

function T(input n: размер задачи):
  if n < некоторая константа k:
    решить задачу относительно n нерекурсивно
  else:
    определить множество из a подзадач, каждая размера n/b
    вызвать функцию T рекурсивно для каждой подзадачи
    объединить решения
end

Дерево решений

В приведённом примере алгоритм рекурсивно разделяет исходную задачу размера n на несколько новых подзадач, каждая размером n/b. Такое разбиение может быть представлено в виде дерева вызовов, в котором каждый узел соответствует рекурсивному вызову, а ветви, исходящие из узла — последующим вызовам для подзадач. Каждый узел будет иметь a ветвей. Также в каждом узле производится объём работы, соответствующий размеру текущей подзадачи n (переданному в данный вызов функции) согласно соотношению $f(n)$ . Общий объём работы алгоритма определяется как сумма всех работ в узлах данного дерева.

Вычислительная сложность подобных алгоритмов может быть представлена в виде рекуррентного соотношения $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$ . Его можно решить путём многократных подстановок выражения $T\left({\frac {n}{b}}\right)$ .[1]

С помощью основной теоремы возможно быстрое вычисление подобных соотношений, что позволяет получить асимптотическую оценку времени работы рекурсивных алгоритмов в нотации O(n) (Θ-нотации), не производя подстановок.

Общая форма

Основная теорема рассматривает следующие рекуррентные соотношения:

T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n),\;\;\;\;{\mbox{где}}\;\;a\geq 1{\mbox{, }}b>1

В применении к анализу алгоритмов константы и функции обозначают:

n — размер задачи.
a — количество подзадач в рекурсии.
n/b — размер каждой подзадачи. (Предполагается, что все подзадачи на каждом этапе имеют одинаковый размер.)
f (n) — оценка сложности работы, производимой алгоритмом вне рекурсивных вызовов. В неё также включается вычислительная стоимость деления на подзадачи и объединения результатов решения подзадач.

Основная теорема позволяет получить асимптотическую оценку для следующих трёх случаев:

Общая форма

Если $f(n)=O\left(n^{c}\right)$ , и выполняется соотношение $c<\log _{b}a$

тогда:

T(n)=\Theta \left(n^{\log _{b}a}\right)

Пример

T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}

Согласно формуле, значения констант и сложности не рекурсивной части задачи:

a=8,\,b=2,\,f(n)=1000n^{2}

f(n)=O\left(n^{c}\right)

, где

c=2

Затем, проверяем, выполняется ли соотношение 1 варианта:

\log _{b}a=\log _{2}8=3>c

.

Следовательно,

T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)

(Для данного примера точное решение рекуррентности даёт $T(n)=1001n^{3}-1000n^{2}$ , при условии $T(1)=1$ ).

Общая форма

Если для некоторой константы k ≥ 0 выполняется:

f(n)=\Theta \left(n^{c}\log ^{k}n\right)

где

c=\log _{b}a

тогда:

T(n)=\Theta \left(n^{c}\log ^{k+1}n\right)

Пример

$T(n)=2T\left({\frac {n}{2}}\right)+10n$

Согласно формуле, значения констант и сложности не рекурсивной части задачи:

a=2,\,b=2,\,c=1,\,f(n)=10n

f(n)=\Theta \left(n^{c}\log ^{k}n\right)

где

c=1,k=0

Проверяем соотношение варианта 2:

\log _{b}a=\log _{2}2=1

, и следовательно,

c=\log _{b}a

В соответствии с 2 вариантом основной теоремы:

T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)

Таким образом, рекуррентное соотношение T(n) равно Θ(n log n).

(Этот результат может быть проверен точным решением соотношения, в котором $T(n)=n+10n\log _{2}n$ , при условии $T(1)=1$ .)

Общая форма

Если выполняется:

f(n)=\Omega \left(n^{c}\right)

где

c>\log _{b}a

а также верно, что:

af\left({\frac {n}{b}}\right)\leq kf(n)

для некоторой константы

k<1

и достаточно больших

n

(так называемое условие regularity condition)

тогда:

T\left(n\right)=\Theta \left(f(n)\right)

Пример

T(n)=2T\left({\frac {n}{2}}\right)+n^{2}

Значения констант и функции:

a=2,\,b=2,\,f(n)=n^{2}

f(n)=\Omega \left(n^{c}\right)

, где

c=2

Проверяем, что выполняется соотношение из варианта 3:

\log _{b}a=\log _{2}2=1

, и, следовательно,

c>\log _{b}a

Также выполняется соотношение regularity condition:

2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}

, при выборе

k=1/2

Следовательно, согласно 3 варианту основной теоремы:

T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).

Данное рекуррентное соотношение T(n) равно Θ(n²), что совпадает с f (n) в изначальной формуле.

(Этот результат подтверждается точным решением рекуррентности, в котором $T(n)=2n^{2}-n$ , при условии $T(1)=1$ .)

Выражения, не решаемые основной теоремой

Следующие соотношения не могут быть решены с применением основной теоремы:[2]

$T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$
a не является константой, для основной теоремы требуется постоянное количество подзадач;
$T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$
между f(n) и $n^{\log _{b}a}$ существует неполиномиальная зависимость;
$T(n)=0.5T\left({\frac {n}{2}}\right)+n$
a<1, но основная теорема требует наличия хотя бы одной подзадачи;
$T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$
f(n) является отрицательной величиной;
$T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$
близко к варианту 3, но не выполняется regularity condition.

Во втором примере разница между $f(n)$ и $n^{\log _{b}a}$ может быть выражена соотношением ${\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}}$ . Из него видно, что ${\frac {1}{\log n}}<n^{\epsilon }$ для любой константы $\epsilon >0$ . Следовательно, разница не является полиномом и основная теорема неприменима.

Применение к некоторым алгоритмам

Алгоритм	Рекуррентное соотношение	Время работы	Примечание
Двоичный поиск	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Основная теорема, 2 вариант: $c=\log _{b}a$ , где $a=1,b=2,c=0,k=0$ [3]
Обход бинарного дерева	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Основная теорема, 1 вариант: $c<\log _{b}a$ где $a=2,b=2,c=0$ [3]
Алгоритм Штрассена	$T(n)=7T\left({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\approx O(n^{2.81})$	Основная теорема, 1 вариант: $c<\log _{b}a$ , где $a=7,b=2,c=2$ [4]
Optimal Sorted Matrix Search	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Теорема Akra-Bazzi для $p=1$ и $g(u)=\log(u)$ для получения $\Theta (2n-\log n)$
Сортировка слиянием	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Основная теорема, 2 вариант: $c=\log _{b}a$ , где $a=2,b=2,c=1,k=0$

См. также

Akra-Bazzi method

Примечания

Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (недоступная+ссылка)
Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
A Master Theorem for Discrete Divide and Conquer Recurrences

Литература

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4. Главы 4.3 (основная теорема) и 4.4 (доказательство)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. — 2nd. — MIT Press and McGraw-Hill, 2001. — ISBN 0-262-53196-8. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73-90. (англ.)
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. (англ.)
CHAPTER 5. RECURSION AND RECURRENCES 5.2 The Master Theorem, CS 21/Math 19 — Course Notes, Ken Bogart and Cliff Stein: Discrete Math in Computer Science.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html

[2] Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (недоступная+ссылка)

[dartmouth-3] Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

[4] A Master Theorem for Discrete Divide and Conquer Recurrences