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

Основная теорема о рекуррентных соотношениях (англ. 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 (переданному в данный вызов функции) согласно соотношению  . Общий объём работы алгоритма определяется как сумма всех работ в узлах данного дерева.

Вычислительная сложность подобных алгоритмов может быть представлена в виде рекуррентного соотношения  . Его можно решить путём многократных подстановок выражения  .[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 Архивная копия от 22 июня 2012 на Wayback Machine
  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 Архивная копия от 21 апреля 2017 на Wayback Machine
  4. A Master Theorem for Discrete Divide and Conquer Recurrences. Дата обращения: 19 августа 2016. Архивировано 18 апреля 2016 года.

ЛитератураПравить