Основная теорема (анализ алгоритмов)

Инструмент для анализа алгоритмов «разделяй и властвуй»

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

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

Введение

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

процедура p(вход x размера n ): если  n < некоторая константа k : Решить x напрямую, без рекурсии, иначе : Создайте подзадачи x , каждая из которых имеет размер n / b. Вызовите процедуру p рекурсивно для каждой подзадачи. Объединить результаты подзадач

Дерево решений.

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

Время выполнения алгоритма, такого как p выше, на входе размера n , обычно обозначаемого , можно выразить рекуррентным соотношением ${\displaystyle T(n)}$

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),}$

где — время создания подзадач и объединения их результатов в вышеописанной процедуре. Это уравнение можно последовательно подставить само в себя и расширить, чтобы получить выражение для общего объема проделанной работы. ^[2] Основная теорема позволяет преобразовать многие рекуррентные соотношения этой формы в Θ-обозначение напрямую, без выполнения расширения рекурсивного соотношения. ${\displaystyle f(n)}$

Общая форма

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

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$

Здесь — размер входной задачи, — количество подзадач в рекурсии, — коэффициент, на который уменьшается размер подзадачи при каждом рекурсивном вызове ( ). Важно, что и не должно зависеть от . Теорема ниже также предполагает, что в качестве базового случая для рекурсии, когда меньше некоторой границы , наименьший размер входных данных, который приведет к рекурсивному вызову. ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b>1}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle T(n)=\Theta (1)}$ ${\displaystyle n}$ ${\displaystyle \kappa >0}$

Рекуррентные соотношения этой формы часто удовлетворяют одному из трех следующих режимов, в зависимости от того, как работа по разделению/рекомбинации задачи соотносится с критическим показателем . (В таблице ниже используется стандартная нотация «большое О» ). ${\displaystyle f(n)}$ ${\displaystyle c_{\operatorname {crit} }=\log _{b}a}$

${\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblems}})/\log({\text{relative subproblem size}})}$

Полезное расширение случая 2 обрабатывает все значения : ^[3] ${\displaystyle k}$

Примеры

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

${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}$

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

${\displaystyle a=8,\,b=2,\,f(n)=1000n^{2}}$, так

${\displaystyle f(n)=O\left(n^{c}\right)}$, где ${\displaystyle c=2}$

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

${\displaystyle \log _{b}a=\log _{2}8=3>c}$.

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

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)}$

(Этот результат подтверждается точным решением рекуррентного соотношения, которое равно , при условии ). ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$ ${\displaystyle T(1)=1}$

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

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n}$

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

${\displaystyle a=2,\,b=2,\,c=1,\,f(n)=10n}$

${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$где ${\displaystyle c=1,k=0}$

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

${\displaystyle \log _{b}a=\log _{2}2=1}$, и, следовательно, c и равны ${\displaystyle \log _{b}a}$

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

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)}$

Таким образом, данное рекуррентное соотношение было в . ${\displaystyle T(n)}$ ${\displaystyle \Theta (n\log n)}$

(Этот результат подтверждается точным решением рекуррентного соотношения, которое равно , при условии ). ${\displaystyle T(n)=n+10n\log _{2}n}$ ${\displaystyle T(1)=1}$

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

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}$

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

${\displaystyle a=2,\,b=2,\,f(n)=n^{2}}$

${\displaystyle f(n)=\Omega \left(n^{c}\right)}$, где ${\displaystyle c=2}$

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

${\displaystyle \log _{b}a=\log _{2}2=1}$, и поэтому, да, ${\displaystyle c>\log _{b}a}$

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

${\displaystyle 2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}}$, выбирая ${\displaystyle k=1/2}$

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

${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).}$

Таким образом, данное рекуррентное соотношение оказалось в , что соответствует исходной формуле. ${\displaystyle T(n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle f(n)}$

(Этот результат подтверждается точным решением рекуррентного соотношения, которое равно , при условии .) ${\displaystyle T(n)=2n^{2}-n}$ ${\displaystyle T(1)=1}$

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

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

• ${\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}$

  a не является константой; количество подзадач должно быть фиксированным

• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}$

  неполиномиальная разность между и (см. ниже; применяется расширенная версия) ${\displaystyle f(n)}$ ${\displaystyle n^{\log _{b}a}}$

• ${\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}$

  ${\displaystyle f(n)}$, что является временем комбинирования, не является положительным

• ${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}$

  случай 3, но нарушение закономерности.

Во втором недопустимом примере выше разница между и может быть выражена отношением . Очевидно, что для любой константы . Следовательно, разница не является полиномиальной, и основная форма Основной теоремы неприменима. Расширенная форма (случай 2b) применима, давая решение . ${\displaystyle f(n)}$ ${\displaystyle n^{\log _{b}a}}$ ${\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}$ ${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$ ${\displaystyle \epsilon >0}$ ${\displaystyle T(n)=\Theta (n\log \log n)}$

Применение к общим алгоритмам

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

• Метод Акра–Бацци
• Асимптотическая сложность

Примечания

1. Бентли, Джон Луис ; Хакен, Доротея ; Сакс, Джеймс Б. (сентябрь 1980 г.), «Общий метод решения повторяющихся задач «разделяй и властвуй»», ACM SIGACT News , 12 (3): 36–44, doi : 10.1145/1008861.1008865, S2CID  40642274, архивировано из оригинала 22 сентября 2017 г.
2. Университет Дьюка, «Большое О для рекурсивных функций: рекуррентные соотношения», http://www.cs.duke.edu/~ola/ap/recurrence.html
3. Чи Яп, Настоящий элементарный подход к основной рекуррентности и обобщениям, Труды 8-й ежегодной конференции по теории и приложениям моделей вычислений (TAMC'11), страницы 14–26, 2011. Электронная копия.
4. Массачусетский технологический институт (MIT), «Основная теорема: практические проблемы и решения», https://people.csail.mit.edu/thies/6.046-web/master.pdf
5. Дартмутский колледж, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

Ссылки

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest и Clifford Stein . Introduction to Algorithms , Second Edition. MIT Press и McGraw–Hill, 2001. ISBN 0-262-03293-7 . Разделы 4.3 (Основной метод) и 4.4 (Доказательство основной теоремы), стр. 73–90. 
• Майкл Т. Гудрич и Роберто Тамассиа . Разработка алгоритмов: основы, анализ и примеры из Интернета . Wiley, 2002. ISBN 0-471-38365-1 . Основная теорема (включая версию случая 2, включенную здесь, которая сильнее, чем версия из CLRS) находится на стр. 268–270.