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

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

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

Введение [ править ]

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

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

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

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

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

${\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 T(n)=\Theta (1)}$${\displaystyle n}$${\displaystyle \kappa >0}$

Повторения этой формы часто удовлетворяют одному из трех следующих режимов, основанных на том, как работа по разделению / рекомбинации проблемы связана с критическим показателем . (В таблице ниже используется стандартная нотация большого O. )${\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}})}$

Дело	Описание	Состояние по отношению к , т.е.${\displaystyle f(n)}$${\displaystyle c_{\operatorname {crit} }}$${\displaystyle \log _{b}a}$	Оценка основной теоремы	Условные примеры
1	Работа по разделению / рекомбинации проблемы затмевается подзадачами. т.е. дерево рекурсии многолистное	Когда где${\displaystyle f(n)=O(n^{c})}$${\displaystyle c<c_{\operatorname {crit} }}$ (ограничено сверху полиномом меньшей степени)	... тогда ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}$ (Член расщепления не появляется; преобладает рекурсивная древовидная структура.)	Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=O(n^{1/2-\epsilon })}$${\displaystyle T(n)=\Theta (n^{1/2})}$
2	Работа по разделению / воссоединению проблемы сравнима с подзадачами.	Когда для${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$${\displaystyle k\geq 0}$ (диапазон ограничен полиномом критического показателя, умноженный на ноль или более необязательных s)${\displaystyle \log }$	... тогда ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)}$ (Граница - это член разделения, когда журнал увеличивается на одну степень.)	Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Theta (n^{1/2})}$${\displaystyle T(n)=\Theta (n^{1/2}\log n)}$ Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Theta (n^{1/2}\log n)}$${\displaystyle T(n)=\Theta (n^{1/2}\log ^{2}n)}$
3	Работа по разделению / воссоединению проблемы преобладает над подзадачами. т.е. дерево рекурсии имеет большое количество корней.	Когда где${\displaystyle f(n)=\Omega (n^{c})}$${\displaystyle c>c_{\operatorname {crit} }}$ (ограниченный снизу полиномом большей степени)	... это не обязательно ничего дает. Кроме того, если ${\displaystyle af\left({\frac {n}{b}}\right)\leq kf(n)}$для некоторого постоянного и достаточно большого (часто называемого условием регулярности )${\displaystyle k<1}$${\displaystyle n}$ тогда в сумме преобладает член разделения :${\displaystyle f(n)}$ ${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)}$	Если и и выполняется условие регулярности, то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Omega (n^{1/2+\epsilon })}$${\displaystyle T(n)=\Theta (f(n))}$

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

Дело	Состояние по отношению к , т.е.${\displaystyle f(n)}$${\displaystyle c_{\operatorname {crit} }}$${\displaystyle \log _{b}a}$	Оценка основной теоремы	Условные примеры
2а	Когда для любого${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$${\displaystyle k>-1}$	... тогда ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)}$ (Граница - это член разделения, когда журнал увеличивается на одну степень.)	Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Theta (n^{1/2}/\log ^{1/2}n)}$${\displaystyle T(n)=\Theta (n^{1/2}\log ^{1/2}n)}$
2b	Когда для${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$${\displaystyle k=-1}$	... тогда ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)}$ (Граница - это член разделения, где обратное значение журнала заменяется повторяющимся журналом.)	Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Theta (n^{1/2}/\log n)}$${\displaystyle T(n)=\Theta (n^{1/2}\log \log n)}$
2c	Когда для любого${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$${\displaystyle k<-1}$	... тогда ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}$ (Граница - это член разделения, при котором журнал исчезает.)	Если и , то .${\displaystyle b=a^{2}}$${\displaystyle f(n)=\Theta (n^{1/2}/\log ^{2}n)}$${\displaystyle T(n)=\Theta (n^{1/2})}$

Примеры [ править ]

Пример случая 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}$, и поэтому, ${\displaystyle c=\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)}$

Таким образом, данное рекуррентное отношение T ( n ) находилось в Θ ( 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).}$

Таким образом, данное рекуррентное соотношение T ( n ) было в ( n ² ), что соответствует 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}}$

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

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

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

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

  ${\displaystyle a<1}$ не может быть меньше одной подзадачи

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

  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)}$

Применение к общим алгоритмам [ править ]

Алгоритм	Повторяющиеся отношения	Время выполнения	Комментарий
Бинарный поиск	${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+O(1)}$	${\displaystyle O(\log n)}$	Примените случай Главной теоремы , где [5]${\displaystyle c=\log _{b}a}$${\displaystyle a=1,b=2,c=0,k=0}$
Обход двоичного дерева	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(1)}$	${\displaystyle O(n)}$	Примените случай Главной теоремы, когда [5]${\displaystyle c<\log _{b}a}$${\displaystyle a=2,b=2,c=0}$
Оптимальный поиск по сортированной матрице	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)}$	${\displaystyle O(n)}$	Примените теорему Акра – Бацци для и, чтобы получить${\displaystyle p=1}$${\displaystyle g(u)=\log(u)}$${\displaystyle \Theta (2n-\log n)}$
Сортировка слиянием	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$	${\displaystyle O(n\log n)}$	Примените случай Главной теоремы , где${\displaystyle c=\log _{b}a}$${\displaystyle a=2,b=2,c=1,k=1}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. 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. 

Внешние ссылки [ править ]

• Teorema Mestre e Exemplos Resolvidos (на португальском языке)