В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 2
Текст из файла (страница 2)
2) Опять достроим дерево д высоты Ь до полного бинарного дерева. Поскольку к листу х подклеивается полное бинарное дерево высоты Ь вЂ” Ь(х), то вместо листа х образуется 2ь ь1*! листьев. Так как общее число листьев в полном бинарном дереве высоты Ь равно 2", то получаем равенство 2, 2~ ~1*! = 2", где суммирование ведется по всем листьям дерева Р. Сокращая на 2", получаем следующее равенство, верное для любого бинарного дерева: где суммирование ведется по всем листьям дерева Р.
Пусть число листьев в дереве Р равно и. По теореме о среднем арифметическом и среднем геометрическом тт положительных чисел имеем п 2л1в1 ~/ ~~ 2л1*1 Ч 2Е. л1в1 т т Отсюда 1 Е Ь(х) > 10яз Лемма доказана. Теперь уже легко доказать слгдуюшее утверждение. Теорема 1.2. Для любого алгоритпма А поиска в ртьорядочвкком массиве из и элвмекотов сиравсдливтл опенки Ьл(тл) )~ ~1обзтл), Йд ттт) )~ 1оязтт. Яоказаотвльствво. Представим алгоритм А в виде бвнарного дерева Р. Тзк как результатом алгоритма может оказаться любой номер т от 1 до а (такой, что а = а), то в дереве Р не меже к листьев. Поэтому утверждение теоремы следует из определения величий л,л(к) и Ьл 1ть) и леммы. 1.2.
Сортировка В качестве еше одного примера рассмотрим задачу сортировки на линейно упорядоченном множестве, которзя обычно ставится сждуюшим образом. Вход: последовательность элементов ам оа,..., а„некоторого пинейно упорядоченного множества (дпя простоты будем считать, что а; ~ а, прн т ф у). Вьюод: перестановка (ть ть ...,т„) элементов 1,2,...,к такая, что ал < от, « ... а;„. Один шаг злгорвтма: сравнение любой пары элементов а; и ад и любое использование полученного ответа а; < а ипи а; > ат.
Алгоритм считаем детерминированным, то есть дпя данного к одноаначно определена пара номеров (т, т) тех элементов, которые сравниваются на первом шаге. В зависимости от одного из двух ответов однозначно определяется пара номеров тех элементов, которые сравниваются на втором шаге н т.д. Таким образом, алгоритм можно представить в виде бнваритно корневого дереве„в котором каждой вершние, отличной от листьев, приписана пара номеров сравниваемых элементов, а лнстьхм дрвпвсаны ответы в виде перестановок (тп тв..., т„).
Определение. Сложностпью Ьл(и) алгвриптма сортпировки А называетсл максвмгльное число вопросов от начала работы до ответа, гдв максимум берется по всем возможным ююдным последовательностзм длвны и. Слозсносятью сартпировки и элементов Ьтьр,(и) нгзываетск птшЕл(и), где минимум беретсг по всем алгоритмам, сортнрующим правильно и элементов. Теорема 1.3.
Ллг любого аггоритпма А, сортаируютцгго п элемеюиов, выиолнгвтпсг нвравенсптвв Ьл(и) > 1обз «!. Яоказатигльстпво. Алгоритм А можно лредставвть в виде бинарного дерева Ю. Любах перестановка (ть тг,..., т„) элементов 1, 2,..., и может быть ответом в алгоритме и, сллповательпо, должна быть приписана хотя бы одному листу.
Поэтому в дереве 1т не менее «1 листьев, Отсюда по леттме 1.1 получаем, что высота дерева Ь(Ю) ) 1обт и!. Но, по'определению Ьл(и) = п(11). Теорема доказана. Следствие 1. Ь„в„,(и) ~ )1обз и!. Использук формулу Стирлинга для и1, лопучаем Следствие 2. Ьтю (и) > (1 — о(1))«1обзи 1'или Ь (и) > «1окг и). Рассьтотрвм далее 2 алгоритма сортировки, сдозптость которых близка к напученной нижней опенке. Сортировка вставками Послеткжательво решаем лодзадачн: отсортировать ап..., аь при й = 1, 2,..., и. При й = 1 (бгзис) ответ тривиален, при й = и получаем ответ всей задачи.
Переход от подзадачи с параметром й — 1 к к дроипхпдит путем вставки в уже упоргдоченную последовательность ат, < а;, « ... а ил элемента аь на соответствующее место. При этом длк аь вмеетсл й возмоввьтх положений: лергд ан, между ат, и а;„..., после а;,, Вставка аь на нужное место осушестзлкетск бвнарвым Теорема 1.4. Сложность алгоритма сортпировки встпавками алан(и) Удовлвитвоугет неРавенстпвУ Ь (и) < 1обз и! + п — 1. Доказаитвльстиво.
Так как при вставке элемента аь вначале вмеегсл Й втхтможньтх наложений: перед а;„между а;, и а;„..., после а;, то длк вставки аь бинарным поиском нужно сделать не более Добз Ц сравнений. Весь алгоритм требует сравненвй не более 11оцг 21+ '~йбзЗ) + (1обз 4~+... + (1ойз и) < 1ойг 2+1обз 3+... +1обз и+ (и-1) = 1ояг п! + п — 1. Следствие 3. Ь, (п) < (1+ о(1))п 1ояг п при и -+ со.
Следствие 4. Й„р„(п) п 1ояг п ири и т оо. Последнее следствие вытекает из следствий 2 и 3. Сортировка слиянием Сортировка слиянием п элементов описывается рекурсивно. Если п = 1, то задача тривиальна. Для п > 2 делим последовательность апаг,,..,а„на 2 последовательности апаг,...,а!ь! и а!ь!+в...,ан, сортируем тем же алгоритмом сортировки слиянием каждую из подпоспеловательностей и затем сливаем 2 полученные отсортированные последовательности А = (а;, < а;, « ... а; ь!) и В = (а, < ад « ...
а,,), формируя отсортированную последовательность Г. На каждом шаге слияния мы сравниваем первые элементы из А и В и переносим меньший из них очередным элементом в С (если А или В становится пустым, то переносим оставшиеся элементы в С по порядку). Пусть |ч,(и) — сложность (число сравнений) алгоритма сортировки слиянием для и элементов в худшем случае, Тогда Ьм(1) = О и Ь~(и) = Ь,„(1г))+Ь ((г!)+п — 1пРи п > 2, посколькУ на слиЯние в худшем случае может потребоваться и — 1 сравнений.
Лемма 1.2. Вм(п) = п!окг и — п+ 1 д от и = 2~, еде я - любое натпуральное число илн я = О. г)окаэательстиво (вндухцией по я). При й = О получаем верное равенство Гол(1) = О. Пусть утверждение леммы верно при всех О < я ( ти — 1, где та - натуральное число. Тогда для к = ти имеем Вм(2 ) = 2Ь„,(2 г)+2'" — 1 = 2(2'" г. (ти — 1) — 2 !+1)+2"' — 1 = ти2 — 2ьт+1, то есть для я = ти утверждение леммы также верно.
Следовательно, оно верно для всех натуральных Й. Теорема 1.5. Ь (и) < 2п1оягп+ 1 для всех натуральных и. Лонаэатпельство. Утверждение теоремы справедливо при и = 1. Пля любого натурального п > 2 найдется натуральное х такое, что 2" ' < и ( 2ь. Функция Хч,(п), очевидно, не убывает с ростом и. Поэтому Ьс (п) < Вел(2ь) = 2" 'я 2ь+1 = 2ь(я 1)+1 < 2п1окг и+1.
Теорема доказана. 2. Рекуррентные методы построения алгоритмов. Одно из важных направлений в построении быстрых алгоритмов — это рекуррентные методы. При этом решение задачи сводится к решению более простых подзадач такого же типа, которые, в свою очередь, сводятся к еше более простым подзадачам и т.д. Естественно при этом должен быть некоторый базисный уровень, задачи которого решаются уже не рекуррентно, а непосредственно. Можно выделить 2 основных рекурревтных метода, которые используются для построения быстрых алгоритмов: метод динамического программирования н метод "разделяй и властвуй" . 2.1.
Метод динамического программирования В самом широхом виде идея динамического программирования состоит в выделении в данной задаче с параметром и (характеризующим дливу входа) подзадач с меньшими параметрами и решении подзадач в соответствии с увеличением параметра, начиная с самого меньшего (обычно 0 или 1). При этом задача с параметром й решается, когда уже решены все подзадачи с параметром Й вЂ” 1 и мевыпе (иногда не Й вЂ” 1, а й — ' с, где с — константа). При этом большого числа подзадач удается часто избежать за счет того, что решение разных подзадач сводится к решению одних и тех же подзадач.
Рассмотрим примеры. Задача об оптимальном порядке умножении матриц. Мы будем рассматривать здесь только обычный способ умножения двух матриц ("строчка на столбец" ) и будем учитывать только число умножение элементов. При этом если матрицы А и В имеют размеры гп х о и а х р, то для вычисления А В требуется, очевидно, гппр умножений элементов. Известно, что для любых трех матриц (АВ)С = А(ВС), то есть произведение матриц не зависит от расстановки скобок. Однако число операций умножения элементов может при этом оказаться разным. Пример.
Пусть матрицы А, В, С имеют размеры о х 1, 1 х п, п х о. Тогда матрица АВ имеет размеры и х п и прн вычислении (АВ)С используется оз+ пз умножений элементов. Матрица ВС имеет размеры 1 х п, поэтому при вычислении А(ВС) используется пз + пз = 2пз умшвкевий элементов, что примерно в -" раз меньше, чем для (АВ)С. Таким образом, имеет смысл следуюпшя задача. Задача. Вход: набор натуральных чисел (тле, п»1,..., и<„) (который задмт размеры натрии в произведении А»Аз °...
А, где А< имеет размеры о»< 1 х та;). Требуетися< расставвть скобки в произведении А1 . Аз ... ° А„ так, чтобы общее число умножений злементов было минимальным, и вычислить это минимальное птсло. Посмотрим сначала, какова сложность тривиального алгоритма, который перебирает все способы расстановки скобок. Пусть а„— число способов правильной расстановки скобок в произведении А1.
Аз ... А„. Теорема 2.1. а„= -„'С~ 'з = ~,~„:1))'-, прв п > 2. Доказан»ельсо»ео. Очевидно, что а» = 1, аз — — 1, аз = 2. Оперения, которую мы сделаем последней в А1 . Аз.... А„, сесе»ит задачу к 2 подзадачам А1 °... А» и А»+1 °.... А„, где 1 < й < и — 1. Поэтому при и) 2 а„= а1а„1+ аза„з +... + а„»а1. Рассмотрим производящую функпию 1(х) = а<х + азхз + азх +...
+ а„х + .. (2.1) Тогда ~ (х) = (а»а<)х + (а»аз + аза»)х + (а»аз + азах + аза») х +... = атх + азх + а<х +... = 1'(х) — а»х = У(х) — х. Таким образом, уз(х) — у(х) + х = О. Решая квадратное уравнение, получаем Дх) = -а<~ —. Поскольку 1(О) — О, то у(х) — -~ —. Раскладывая у (х) в ряд Тейлора и сравнивая с (2.1), получаем (проверьте): 1 3 5 2п — 3 4" ' 2 2 2 2 п! 2ь-1(2„ т»! ( и!(2 4 . 6 - . (2т< — 2)) 2" 1(2а — 2)! 1 и!2" 1(п — 1)' п Теорема доказана. Зааечание. Для полной строгости в доказательстве нужно обсудить существование функции у(х), заданной равенством (2.1). Можно показать, что ряд справа скодится, например, при О < х < 1. Раскрывая факториалы по формуле Стирлинга, легко получить, 4"' что С~~ т<--, то есть а„растет зкспоненпиально с ростом п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
