Русская Википедия:Основная теорема о рекуррентных соотношениях

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Описание

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

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

В приведённом примере алгоритм рекурсивно разделяет исходную задачу размера 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>

См. также

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations". Шаблон:Wayback.
  2. ↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions"Шаблон:Недоступная ссылка.
  3. ↑ 3,0 3,1 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Шаблон:Wayback
  4. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Основная_теорема_о_рекуррентных_соотношениях&oldid=10529760