(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 7

Однако алгоритм, приведённый ниже и имеющийсложность такую же, как алгоритм Прима, решает задачуКРАТЧАЙШИЙ ПУТЬ В ГРАФЕ (докажите корректностьэтого алгоритма, см., например, (2 ), стр. 1 1 ).Алгоритм-5 Алгоритм КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ в одну вершину______Вход: п > 0, dtj > 0, Vi j € (1,.... п)Выход: Кратчайший путь из любой вершиныо, вvn.for all г £ l..n doPi ={Nvll, +oo) {сбрасываем начальные оценки}end forfor all j € {j.: djtn < Too} doPj s (n, dJn) {устанавливаем оценки для соседей}end forfor all iteration e l..n do {достаточно, чтобы процесс сошелся}for all i £ l..n do {по всем узлам}for all j e (j : d,j < +oo} do {по всем соседямif Д > Dj + <%then {j-й сосед предлагает нам лучший путь}А +- Dj + dy {улучшаем оценку}Pi = (Т А) {направляем путь к .?'-му соседу}end ifend forend forend forreturn Vi (/';!).

Ррцщ!), РщщщО)-.. •, n) {Or всех узлов прокладываем путь к№»}Теперь мы обратимся к описанию известных методовполучения полиномиальных алгоритмов и к примерам задач,на которых эти методы хорошо иллюстрируются.ПОИСК В УПОРЯДОЧЕННОМ МАССИВЕ.УСЛОВИЕ. Имеется упорядоченный линейно массив чисел«1 < а2<...< ап и элемент а, совпадающий с одним из а\.ВОПРОС. Чему равен номер элемента, с которым совпадает а?Замечание.

Сформулируйте также и эту задачу как задачураспознавания.Конечно, есть простой алгоритм, решающий эту задачу заполиномиальное время (какой?). Однако имеет местоследующаяТеорема 2.1. Существует алгоритм Л, для которогомаксимальное число сравнений равно Гlog2n \ .Предъявите нужный алгоритм и докажите, что онправильно работает (для справки см. (4), стр. 5;соответствующий алгоритм называется «поиск в бинарномдереве» и определяется с помощью рекурсии).Доказать утверждение типа «для любого алгоритма»обычно существенно труднее, чем утверждение типа«существует алгоритм».

В первом случае нужно чёткоописать весь класс рассматриваемых алгоритмов. Вышебыло указано, что любой алгоритм поиска в упорядоченноммассиве из п элементов можно представить в виде бинарногодерева. Поэтому далее мы рассмотрим некоторые свойствабинарных деревьев.Определение. Глубиной h(x) листа х в корневом деревеD будем называть число ребер в (единственном) пути изкорня дерева в лист х. Высотой h(D) дерева D будемназывать тах{/г(х)}, где максимум берется по всем листьямдерева D. Средней высотой hcp(D) дерева D будем называтьсреднее арифметическое величин h (х) по всем листьямдерева D.Лемма 2.2.

Для любого бинарного дерева с п листьямивыполнены неравенства:1) h(D)>riog2n 1;2) hcp(D)>log2n.Докажите эту лемму самостоятельно (для справки см. (4),стр. 6 )Следствие. Для всякого алгоритма А поиска вупорядоченном массиве сложность А >Tlog^n](длядоказательства достаточно представить А в виде бинарногодерева, в котором не менее п листьев).СОРТИРОВКАВОПРОС. Дана последовательность различных элементовнекоторого линейно упорядоченного множестваУСЛОВИЕ.

Выстроить элементы в порядке возрастания.Соответствующий алгоритм А упорядочения можнопредставить в виде бинарного корневого дерева, каждойвершине которого приписана пара сравниваемых элементов, алистьям приписаны ответы в виде перестановок. Обозначимчерез L(ri)=min LA(n). где min берётся по всем алгоритмам А, аЬА(п) есть сложность алгоритма сортировки А и равнамаксимальному числу сравнений от начала работы до ответа.Теорема 2.3.

LA(n) >log2n!.Для доказательства достаточно представить А в видебинарного дерева и заметить, что любая последовательностьэлементов м.б. ответом и в силу этого должна быть приписанахотя бы одному листу, а тогда в дереве не менее п! листьев иего высота не меньше log2n! (отсюда немедленно следует, чтосложность алгоритма сортировки (любого!) не менее log2n!. Всилу формулы Стирлинга имеем, Up) > (1 -0(п)) log2n.Рассмотрим теперь алгоритм «сортировка слиянием», чьяоценка окажется близка сверху к полученной. Алгоритм«СОРТ» будет работать следующим рекурсивным образом:последовательность элементов делится на две почти равныечасти А и В и каждую часть упорядочиваем, а затем сливаемотсортированные последовательности вместе в С (для деталейсм.

(4), стр.9). На каждом шаге слияния сравниваем первыеэлементыизполученныхотсортированныхподпоследовательностей А я В я меньший из них переносимочередным элементом в С (если А или В уже пусто, тооставшиеся элементы переносим в С по порядку). Если Ьа(п)- число сравнений, то£с,( 1)=0, a Lc„(ri)=Lc,$_n/2J)+ Д,(Гп/2~\)+п- 1 при п> 2 .Лемма 2.4.

LCJ(n)=nlog2 n-n+l для п=2к.Доказательство проводится индукцией по к (докажите сами!).В качестве следствия получаем, что La,,(n) < 2nlog2n+\(докажите следствие сами: используйте индукцию или см. длясправки (4), стр.9). Обратимся теперь к общим методамполучения быстрых алгоритмов.РЕКУРРЕНТНЫЕ МЕТОДЫ ПОСТРОЕНИЯАЛГОРИТМОВОдно из важных направлений в построении быстрыхалгоритмов - это рекуррентные методы. При этом решениезадачи сводится к решению более простых подзадач такого жетипа, которые, в свою очередь, сводятся к еще более простымподзадачам и т.д. Естественно, при этом должен бытьнекоторый базисный уровень, задачи которого решаются уже нерекуррентно, а непосредственно. Можно выделить два основныхрекуррентных метода, которые используются для построениябыстрых алгоритмов: метод динамического программированияи метод «разделяй и властвуй».

Для этих основных методовможно привести очень простые и наглядные примеры,которые будут понятны любому читателю: задача обоптимальном порядке умножения матриц и алгоритмКарацубы для умножения чисел1. Метод динамического программированияВсамомширокомвидеидеядинамическогопрограммирования состоит в выделении в данной задаче спараметром п (характеризующим длину входа) подзадач сменьшими параметрами и решении подзадач в соответствии сувеличением параметра, начиная с самого меньшего (обычно Оили 1). При этом задача с параметром к решается, когда ужерешены все подзадачи с параметром к - 1 и меньше (иногда не к 1, а к - с, где с - константа).

При этом большого числа подзадачудается часто избежать за счет того, что решение разныхподзадач сводится к решению одних и тех же подзадач.Рассмотрим пример.Задача об оптимальном порядке умножения матрицМы будем рассматривать здесь только обычный способумножения двух матриц («строчка на столбец») и будемучитывать только число умножений элементов.

При этом , еслиматрицы А и В имеют размеры т х п и п х р , т о для вычисленияА • В требуется, тпр умножений элементов. Известно, что длялюбых трех матриц (АВ)С - А(ВС), то есть произведениематриц не зависит от расстановки скобок. Однако числоопераций умножения элементов может при этом оказатьсяразным.Рассмотрим вычисление произведения п матрицЛ) = А4,хА/гХ .

. , хМ тгде М{ - матрица с г\А строками и г; столбцами. Порядок, вкотором эти матрицы перемножаются, может существенносказаться на общем числе операции, требуемых длявычисления М, независимо от алгоритма, применяемого дляумножения матриц.Пример Рассмотрим произведениеМ=> М, У М, X М, ХМ,[10x20] [20 x 50] [50x1 J [1x100]где размеры каждой матрицы М\ указаны в скобках. Есливычислять М в порядкеМ, X(M.t х (М, х М,)), хо потребуется125 000 операций, тогда как вычисление М в порядке(Mj X(М%XЩ)) X М, занимает лишь 2 2 0 0 операций.Процесс перебора всех порядков, в которых можновычислить рассматриваемое произведение п матриц с цельюминимизировать число операций, имеет экспоненциальнуюсложность, что при больших « практически неприемлемо.Однако динамическое программирование приводит калгоритму сложности О(п3). Пусть т-у - минимальнаясложность вычисления произведенияl < i < j < n .

Очевидно, чтоX^[ О,1+1е слиX * * *XAfy,I = /,тч “ \MIN (»Чк+тш , + г,...,г / Л , если / > {,<< * < /Здесьmik -минимальнаясложностьaвычисления- минимальнаяСЛОЖНОСТЬ вычисления^+Третье слагаемое равно сложности умножения М' на М".Заметим, что М’ — матрица размера r,_,x rh а М" - матрицаразмера гкх г.При динамическом программировании т,у вычисляются впорядке возрастания разностей нижних индексов.

Начинают свычисления ти для всех /, затем m,k+i для всех /, потом т,л+2 ит. д. При этом т,к и тМ} будут уже вычислены, когда мыприступим к вычислению ту . Это следует из того, что при i <к < j, разность j-i должна быть больше k-i, а также и j-(k+ 1).Соответствующий алгоритм приведён на рис 2.4.1.2.3.4.5.6.beginlor (я—1 until п do0;for /'■*— 1 until л—1 dofor ( ‘—1 u n t il /; —1 dobeginJ1+ ('>in,,*- M I N (W/ft+ Щ+,‘ K-kiiwrite tnlneitdРис. 2.4 Алгоритм динамического программирования для определенияпорядка умножения матриц.0%=>04 -io o o ffIDjj ** 100Q% *»ш о% *3000даи«50002200Рис.

2.5 Сложности вычисления произведений M i х М ;+1 х ... х М j.Для оценки сложности тривиального (переборного)алгоритма и приведённого выше см. (4), стр. 10-12, однако нетрудно сообразить, что сложность алгоритма динамическогопрограммирования не более чем полиномиальна (для другогопримера см. (4), стр. 13, задача о кратчайших путях вориентированном графе).2. Метод «разделяй и властвуй».

Теорема орекуррентном неравенствеДругой рекуррентный метод построения быстрыхалгоритмов - это метод, который называют «разделяй ивластвуй». В нем также решение задачи сводится крешению подзадач, но, в отличие от метода динамическогопрограммирования, размерность подзадач отличается отразмерности задачи не на константу, а в константу раз иподзадачи решаются независимо друг от друга. Дляполученияоценоксложноститакихалгоритмовиспользуется следующая теорема:Теорема 2.5.