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

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

Не все рекурсивные соотношения могут быть решены с помощью основной теоремы. Существует несколько её обобщений, в том числе Шаблон:Iw.

Описание

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

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

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

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

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

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

Общая форма

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

$T(n)=aT\left(\frac{n}{b}\right)+f(n),\text{где}a⩾1,b>1.$

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

n — размер задачи.

a — количество подзадач в рекурсии.

n/b — размер каждой подзадачи. (Предполагается, что все подзадачи на каждом этапе имеют одинаковый размер.)

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

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

Вариант 1

Общая форма

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

$T(n)=\mathrm{\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(n^c)$, где $c=2$.

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

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

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

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

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

Вариант 2

Общая форма

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

$f(n)=\mathrm{\Theta }(n^c{\log }^{k}n)$, где $c={\log }_{b}a$.

Тогда

$T(n)=\mathrm{\Theta }(n^c{\log }^{k+1}n).$

Пример

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

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

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

$f(n)=\mathrm{\Theta }(n^c{\log }^{k}n)$, где $c=1,k=0$.

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

${\log }_{b}a={\log }_{2}2=1$, и следовательно, $c={\log }_{b}a$.

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

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

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

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

Вариант 3

Общая форма

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

$f(n)=\mathrm{\Omega }(n^c)$, где $c>{\log }_{b}a$,

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

$af\left(\frac{n}{b}\right)⩽kf(n)$ для некоторой константы $k<1$ и достаточно больших $n$ (так называемое условие регулярности), тогда

$T(n)=\mathrm{\Theta }(f(n)).$

Пример

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

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

$a=2,b=2,f(n)=n^2,$

$f(n)=\mathrm{\Omega }(n^c)$, где $c=2$.

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

${\log }_{b}a={\log }_{2}2=1$, и, следовательно, $c>{\log }_{b}a$.

Также выполняется условие регулярности:

$2\left(\frac{n^2}{4}\right)⩽k{n}^2$ при выборе $k=1/2$.

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

$T(n)=\mathrm{\Theta }(f(n))=\mathrm{\Theta }(n^2).$

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

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

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

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

• $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, но не выполняется условие регулярности.

Во втором примере разница между $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$
Обход двоичного дерева	$T(n)=2T\left(\frac{n}{2}\right)+O(1)$	$O(n)$	Основная теорема, 1 вариант: $c<{\log }_{b}a$ где $a=2,b=2,c=0$
Алгоритм Штрассена	$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$
Шаблон:Lang-en2	$T(n)=2T\left(\frac{n}{2}\right)+O(\log n)$	$O(n)$	Теорема Акра-Баззи для $p=1$ и $g(u)=\log (u)$ для получения $\mathrm{\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$

См. также

• Теорема Акра-Баззи

Литература

• Шаблон:Книга Главы 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.