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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Описание[править | править код]

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

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

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

Вычислительная сложность подобных алгоритмов может быть представлена в виде рекуррентного соотношения . Его можно решить путём многократных подстановок выражения .[1]

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

Общая форма[править | править код]

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

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

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

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

Вариант 1[править | править код]

Общая форма[править | править код]

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

тогда:

Пример[править | править код]

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

, где

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

.

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

(Для данного примера точное решение рекуррентности даёт , при условии ).

Вариант 2[править | править код]

Общая форма[править | править код]

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

где

тогда:

Пример[править | править код]

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

где

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

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

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

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

(Этот результат может быть проверен точным решением соотношения, в котором , при условии .)

Вариант 3[править | править код]

Общая форма[править | править код]

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

где

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

для некоторой константы и достаточно больших (так называемое условие regularity condition)

тогда:

Пример[править | править код]

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

, где

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

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

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

, при выборе

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

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

(Этот результат подтверждается точным решением рекуррентности, в котором , при условии .)

Выражения, не решаемые основной теоремой[править | править код]

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

  • a не является константой, для основной теоремы требуется постоянное количество подзадач;
  • между f(n) и существует неполиномиальная зависимость;
  • a<1, но основная теорема требует наличия хотя бы одной подзадачи;
  • f(n) является отрицательной величиной;
  • близко к варианту 3, но не выполняется regularity condition.

Во втором примере разница между и может быть выражена соотношением . Из него видно, что для любой константы . Следовательно, разница не является полиномом и основная теорема неприменима.

Применение к некоторым алгоритмам[править | править код]

Алгоритм Рекуррентное соотношение Время работы Примечание
Двоичный поиск Основная теорема, 2 вариант: , где [3]
Обход бинарного дерева Основная теорема, 1 вариант: где [3]
Алгоритм Штрассена Основная теорема, 1 вариант: , где [4]
Optimal Sorted Matrix Search Теорема Akra-Bazzi для и для получения
Сортировка слиянием Основная теорема, 2 вариант: , где

См. также[править | править код]

Примечания[править | править код]

  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 (недоступная ссылка)
  3. 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
  4. 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.