Основная теорема о рекуррентных соотношениях — результат, использующийся в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй», например, при оценке времени их выполнения. Теорема была введена и доказана Джоном Бентли, Доротеном Хакеном и Джеймсом Хакеном в 1980 году. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была приведена.
Не все рекурсивные соотношения могут быть решены с помощью основной теоремы. Существует несколько её обобщений, в том числе теорема Акры — Баззи, дающая оценку для случая, когда подзадачи имеют существенно разные размеры.
Описание Рассмотрим задачу, которую можно решить рекурсивным алгоритмом:
function T(input n: размер задачи): if n < некоторая константа k: решить задачу относительно n нерекурсивно else: определить множество из a подзадач, каждая размера n/b вызвать функцию T рекурсивно для каждой подзадачи объединить решения end
В приведённом примере алгоритм рекурсивно разделяет исходную задачу размера n на несколько новых подзадач, каждая размером n/b. Такое разбиение может быть представлено в виде дерева вызовов, в котором каждый узел соответствует рекурсивному вызову, а ветви, исходящие из узла — последующим вызовам для подзадач. Каждый узел будет иметь a ветвей. Также в каждом узле производится объём работы, соответствующий размеру текущей подзадачи n (переданному в данный вызов функции) согласно соотношению . Общий объём работы алгоритма определяется как сумма всех работ в узлах данного дерева.
Вычислительная сложность подобных алгоритмов может быть представлена в виде рекуррентного соотношения . Его можно решить путём многократных подстановок выражения .Duke University, «Big-Oh for Recursive Functions: Recurrence Relations». .
С помощью основной теоремы возможно быстрое вычисление подобных соотношений, что позволяет получить асимптотическую оценку времени работы рекурсивных алгоритмов в нотации O(n) (Θ-нотации), не производя подстановок.
Общая форма Основная теорема рассматривает следующие рекуррентные соотношения:
В применении к анализу алгоритмов константы и функции обозначают: n — размер задачи. a — количество подзадач в рекурсии. n/b — размер каждой подзадачи. (Предполагается, что все подзадачи на каждом этапе имеют одинаковый размер.) f (n) — оценка сложности работы, производимой алгоритмом вне рекурсивных вызовов. В неё также включается вычислительная стоимость деления на подзадачи и объединения результатов решения подзадач.
Основная теорема позволяет получить асимптотическую оценку для следующих трёх случаев:
Вариант 1
Общая форма Если , и выполняется соотношение , тогда:
Пример
Согласно формуле, значения констант и сложности нерекурсивной части задачи:
, где .
Затем проверяем, выполняется ли соотношение 1-го варианта: .
Следовательно,
(Для данного примера точное решение рекуррентности даёт , при условии .)
Вариант 2
Общая форма Если для некоторой константы выполняется
, где .
Тогда
Пример
Согласно формуле, значения констант и сложности не рекурсивной части задачи:
, где .
Проверяем соотношение варианта 2: , и следовательно, .
В соответствии с 2-м вариантом основной теоремы,
Таким образом, рекуррентное соотношение T(n) равно Θ(n log n).
(Этот результат может быть проверен точным решением соотношения, в котором , при условии .)
Вариант 3
Общая форма Если выполняется
, где ,
а также верно, что
для некоторой константы и достаточно больших (так называемое условие регулярности), тогда
Пример
Значения констант и функции:
, где .
Проверяем, что выполняется соотношение из варианта 3: , и, следовательно, .
Также выполняется условие регулярности:
при выборе .
Следовательно, согласно 3-му варианту основной теоремы,
Данное рекуррентное соотношение T(n) равно Θ(n2), что совпадает с f(n) в изначальной формуле.
(Этот результат подтверждается точным решением рекуррентности, в котором , при условии .)
Выражения, не решаемые основной теоремой Следующие соотношения не могут быть решены с применением основной теоремы:Massachusetts Institute of Technology (MIT), «Master Theorem: Practice Problems and Solutions».
a не является константой, для основной теоремы требуется постоянное количество подзадач.
Между f(n) и существует неполиномиальная зависимость.
a < 1, но основная теорема требует наличия хотя бы одной подзадачи.
f(n) является отрицательной величиной.
Близко к варианту 3, но не выполняется условие регулярности.
Во втором примере разница между и может быть выражена соотношением Из него видно, что для любой константы . Следовательно, разница не является полиномом, и основная теорема неприменима.
Применение к некоторым алгоритмам Алгоритм Рекуррентное соотношение Время работы Примечание Двоичный поиск Основная теорема, 2 вариант: , где Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Обход двоичного дерева Основная теорема, 1 вариант: где Алгоритм Штрассена Основная теорема, 1 вариант: , где Теорема Акры — Баззи для и для получения Сортировка слиянием Основная теорема, 2 вариант: , где
Примечания
Литература Главы 4.3 (основная теорема) и 4.4 (доказательство) 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.
Категория:Теория сложности вычислений Категория:Рекурсия Категория:Анализ алгоритмов