Основная теорема (анализ алгоритмов) - Master theorem (analysis of algorithms)

В анализе алгоритмов , то мастер - теорема для разделяй и властвуй рецидивами обеспечивает асимптотический анализ ( с помощью Big O обозначения ) для рекуррентных соотношений типов , которые происходят в анализе многих алгоритмов и властвуй . Этот подход был впервые представлен Джоном Бентли , Доротеей Хакен и Джеймсом Б. Саксом в 1980 году, где он был описан как «объединяющий метод» для решения таких повторений. Название «основная теорема» было популяризировано в широко используемом учебнике по алгоритмам « Введение в алгоритмы » Кормена , Лейзерсона , Ривеста и Стейна .

Не все рекуррентные соотношения могут быть решены с помощью этой теоремы; его обобщения включают метод Акра – Бацци .

Вступление

Рассмотрим проблему, которую можно решить с помощью рекурсивного алгоритма, например следующего:

procedure p(input x of size n):
    if n < some constant k:
        Solve x directly without recursion
    else:
        Create a subproblems of x, each having size n/b
        Call procedure p recursively on each subproblem
        Combine the results from the subproblems
Дерево решений.

Вышеупомянутый алгоритм рекурсивно делит проблему на ряд подзадач, причем каждая подзадача имеет размер n / b . Его дерево решений имеет узел для каждого рекурсивного вызова, а дочерние элементы этого узла являются другими вызовами, сделанными из этого вызова. Листья дерева - это базовые случаи рекурсии, подзадачи (размером меньше k ), которые не рекурсивны. В приведенном выше примере будет иметь дочерние узлы на каждом узле без листьев. Каждый узел выполняет объем работы, который соответствует размеру подзадачи n, переданной этому экземпляру рекурсивного вызова и предоставленной . Общий объем работы, выполненной всем алгоритмом, - это сумма работы, выполненной всеми узлами в дереве.

Время выполнения алгоритма, такого как 'p' выше, на входе размера 'n', обычно обозначаемом , может быть выражено рекуррентным соотношением

где время для создания подзадач и объединения их результатов в описанной выше процедуре. Это уравнение можно последовательно подставлять в себя и расширять, чтобы получить выражение для общего объема проделанной работы. Основная теорема позволяет напрямую преобразовать многие рекуррентные отношения этой формы в Θ-нотацию без расширения рекурсивного отношения.

Общая форма

Основная теорема всегда дает асимптотически точные границы рекуррентности из алгоритмов «разделяй и властвуй», которые разбивают входные данные на более мелкие подзадачи равного размера, рекурсивно решают подзадачи, а затем объединяют решения подзадач, чтобы дать решение исходной проблемы. Время для такого алгоритма может быть выражено путем добавления работы, которую они выполняют на верхнем уровне своей рекурсии (чтобы разделить проблемы на подзадачи и затем объединить решения подзадач), вместе со временем, затраченным на рекурсивные вызовы алгоритма. Если обозначает общее время для алгоритма на входе размера и обозначает количество времени, затрачиваемое на верхний уровень повторения, то время может быть выражено соотношением повторения, которое принимает форму:

Вот размер входной задачи, это количество подзадач в рекурсии и фактор, на который размер подзадачи уменьшается при каждом рекурсивном вызове (b> 1). В приведенной ниже теореме также предполагается, что в качестве базового случая для повторения, когда меньше некоторой границы , наименьший размер ввода, который приведет к рекурсивному вызову.

Повторения этой формы часто удовлетворяют одному из трех следующих режимов, основанных на том, как работа по разделению / рекомбинации проблемы связана с критическим показателем . (В таблице ниже используется стандартная нотация большой буквы O. )

Случай Описание Состояние по отношению к , т.е. Оценка основной теоремы Условные примеры
1 Работа по разделению / рекомбинации проблемы затмевается подзадачами.

т.е. дерево рекурсии многолистное

Когда где

(ограничено сверху полиномом меньшей степени)

... тогда

(Член расщепления не появляется; преобладает рекурсивная древовидная структура.)

Если и , то .
2 Работа по разделению / воссоединению проблемы сравнима с подзадачами. Когда для

(диапазон ограничен полиномом критического показателя, умноженный на ноль или более необязательных s)

... тогда

(Граница - это член разделения, когда журнал увеличивается на одну степень.)

Если и , то .

Если и , то .

3 Работа по разделению / воссоединению проблемы преобладает над подзадачами.

т.е. дерево рекурсии имеет большое количество корней.

Когда где

(ограниченный снизу полиномом большей степени)

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

тогда в сумме преобладает член разделения :

Если и и выполняется условие регулярности, то .

Полезное расширение Case 2 обрабатывает все значения :

Случай Состояние по отношению к , т.е. Оценка основной теоремы Условные примеры
Когда для любого ... тогда

(Граница - это член разделения, когда журнал увеличивается на одну степень.)

Если и , то .
2b Когда для ... тогда

(Граница - это член разделения, где обратное значение журнала заменяется повторяющимся журналом.)

Если и , то .
2c Когда для любого ... тогда

(Граница - это член разделения, при котором журнал исчезает.)

Если и , то .

Примеры

Пример случая 1

Как видно из приведенной выше формулы:

, так
, куда

Затем мы посмотрим, удовлетворяем ли мы условию случая 1:

.

Из первого случая основной теоремы следует, что

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

Пример случая 2

Как видно из приведенной выше формулы, переменные принимают следующие значения:

куда

Затем мы посмотрим, удовлетворяем ли мы условию случая 2:

, а значит, c и равны

Итак, это следует из второго случая основной теоремы:

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

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

Пример случая 3

Как видно из приведенной выше формулы, переменные принимают следующие значения:

, куда

Затем мы посмотрим, удовлетворяем ли мы условию случая 3:

, а значит, да,

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

, выбирая

Итак, это следует из третьего случая основной теоремы:

Таким образом, данное рекуррентное соотношение было в том , что соответствует исходной формуле.

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

Недопустимые уравнения

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

  • а не является константой; количество подзадач должно быть исправлено
  • неполиномиальная разница между и (см. ниже; применяется расширенная версия)
  • не может быть меньше одной подзадачи
  • , которое является временем комбинации, не является положительным
  • случай 3, но нарушение регулярности.

Во втором недопустимом примере выше разница между и может быть выражена соотношением . Понятно, что для любой константы . Следовательно, разница не является полиномиальной, и основная форма основной теоремы не применяется. Расширенная форма (случай 2b) действительно применяется и дает решение .

Применение к распространенным алгоритмам

Алгоритм Повторяющиеся отношения Время выполнения Комментарий
Бинарный поиск Примените случай Главной теоремы , где
Обход двоичного дерева Примените случай основной теоремы, где
Оптимальный поиск по сортированной матрице Примените теорему Акра – Бацци для и, чтобы получить
Сортировка слиянием Примените случай Главной теоремы , где

Смотрите также

Примечания

использованная литература

внешние ссылки