В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 3
Текст из файла (страница 3)
Следовательно переборный алгоритм имеет экспоненциальную сложность. 11 Теорема 2.2. Юля нахождения оптпимольного порядка умножекия и моторин сутцестпвуетп алгоринтм (тпипв динамического программирования) с числом операций (ориуметпичвскве и сравнений чисел) 0(пз) . Воказонтельстпво. Пусть на вход поступает набор чисел (тпв,нть...,тп ). Введем такие подзадачи Втс найти оптимальный порядок вычислений и наименьшее число кб умножений элементов для произведения Ат х Атчп х ... х А, (1 < т' < т' < п), Очевидно, кн = О для всех т, н общее число подзадач ВО есть 0(пз).
Ъ'твержденне. Если 1 < т < т' < п, тпо (2.2) йт = шш(lттл+ стыд+ пв ттпттпт), где минимум беретпся ио всем в отеките, чтпо т < в < т' — 1. Доказатпельстпво. Если последняя операция умножения делит произведение Ат Аьтт ... Аз на 2 произведения (А; ... А,) (А,+г... Ад), то для получения минимального числа оцерацвй надо использовать минимальное число операций в обеих скобках, то есть всего асти + йт+ту операций. После вычисления этих произведений надо еще перемножить 2 матрицы размеров ттн т х тпт и тпт х тп,. Получаем общее число онераций, стоящее в (2.2) в фигурных скобках. Теперь остается заметить, что для минимизации общего числа умножений достаточно перебором выбрать оцтимальное место для последней операции.
Утверждение доказано. Будем решать подзадачи ВО ярусами, относя к ярусу 1 все подзадачи с у — т = й Рассмотрим последовательно Ф = О, 1, 2,..., п — 1. При Ф = О получим подзадачи Вн, для которых кз = О и скобки вообще не надо расставлять. При решении очередной задачи ВО с т — т = 1 воспользуемся утверждением. При этом легко видеть, что справа в (2.2) будут использоваться результаты подзадач ярусов тт < 1, которые уже решены. Тогда для вычисления утз по формуле (2.2) достаточно сделать 2(у-т) умножений, 2(т — т) сложений и т' — т — 1 сравнений.
Общее число операций для вычисления одного йб не превосходит 0(п), а для вычисления всех ку — не превосходит 0(пз) (поскольку общее число подзадач Ву есть 0(из)). При вычислении йт указанным способом мы накопим и то в, для которою достигается минимум в (2.2). Если мы для всех (т, т') будем фвхснровать это в, то сможем быстро оптимально расставить скобки в задаче Вгв (в исхтвшой задаче), разбивая каждое ироивведение последовательно оптимельным образом на 2 произвевпния. Теорема доказана. Задача о кратчайших путях Пусть 0 — полный ориентированный граф с и вершинами иь эз,..., и„. Пусть каждой дуге (иь о ) сопоставлено действительное число4, > О,либоат =+со.Числодт трактуетсякакрасстояниензит в о.
"напрямую". Ллина ориентированного пути из сз в и. определяется как сумма длин всех дуг этого пути (она равна +ос, если хотя бы одно слагаемое равно +со). Кратчайшее расстояние 4 из ит в и. определим как минимум длин по всем ориентированным путям из гц в ор Соответствующий путь будем называть кратчайшим. Рассмотрим следующую задачу о кратчайших путях. Вход: матрица Р = ))атт)) порядка и (считаем, что дз = О для всех т). Требуетпсят построить матрицу Р = )Щт.)) кратчайших расстояний. Отметим, что аналогичную задачу для неполного графа можно свести к задаче о полном графе, положив тттт. — — +сю для несуществующих дуг. Если дт = дтз для всех т',), то граф С можно считать неорнентированным. Алгоритм для указанной задачи, основанный на переборе всех возможньпс путей, имеет не менее, чем зкспоненпнвльную сложность, поскольку из тц в и существует не менее (и — 2)! путей без повторяющихся вершин.
Теорема 2.3. Сушестпвуетп алгоритпм для задачи о кратчайших путпях, стпрояший по матприце Р матприцу .Р, с числом операций (арифметических и сравнений чисел) 0(п~), где п — число вершин в графе. Яокагательство. Введем следующие подзадачи: для каждой пары т,) н натурального к > О вычислить а,:, — минимальную длину Л») среди всех ориентированных путей из ся в и;, проходящих,.
кроме ит и о, только по вершинам иь ом..., о» (возможно только по части или напрямую из и, в и ). Если й = О, то разрешается только переход из о; в и "напрямую". Пусть Р<") = ))ат'.))). Тогда Р~в) = Р н Ргт) = Р. Будем последовательно вычислять РО), Рт'),..., Р»"). Утверждение. Для любых т,) и й > О а(») .,а(»-т) д(»-т) ат»-т)) О =ттп(О м +»т Доказатпельстпво. Все пути из эт в о-, использующие только вершины оп из,...,и», распадаются на 2 множества А и  — не проходящих через и» и проходящих через и».
Минимальная длина путей в А равна тз 4 ь-1) по определению. Каждый путь из В разбивается на 2 части: путь В) из о; в иь по вершинам опии,оь ) и путь Вз из оь в иу по вершннам оп из,..., оь ь Минимальная длина пути в Вт равна а — а . аа, а в Вз — аь) . Сравнивал т)с и д(ь + дь., получаем аб . зать) Утверждение доказано.
Замечание. Вычисляя дб описанным способом, мы, в частнос(ь) ти, узнаем, использовать иь или нет. Тахим образом, для вычисления Ррб по РО ') достаточно пз сложеннй и пз сравнений чисел, а для вычисления,РО), Р1з),..., Р)") = Р по заданной матрипе .Р = Р1ч) достаточно пз сложений и пз сравнений. Теорема доказана.
При этом, учитывая замечание, можно быстро установить и сами кратчайшие пути. 2.2. Метод "разделяй и властвуй". Теорема о рекуррентном неравенстве Лругой рекуррентный метод построения быстрых алгоритмов— это метод, который называют "разделяй и властвуй". В нем также решение задачи сводится к решению подзадач, но, в отличие от метода динамического программирования, рвэмерность подзадач отличается от размерности задачи не на константу, а в константу раз н подзадачи решаются независимо друг от друга. Лля получения оценок сложности таких алгоритмов используется следующая теорема. Теорема 2.4 (о рекуррентном неравенстве).
Пустпь Цп) — функция натпурального параметпра и. Пусть с — натпуральное число, с > 2, и а, б,а - дет)стпвитпельные констпантпы, причем а > О, и пустпь для всех и = сь, где б — любое натпуральное число (б = 1,2,3,...), выполняетпся неравенстпво (2.3) Ь(п) < аЬ( — )+б Пустпь при этом Цп) монотпонно не убьыаетп на каждом отпреэке [с- + 1,с"+)).
Тогда при стпремлении и к бесконечности для всех и выполняетпся 0(п~), если а > 1о3,а, Цп) = 0(п)еа"), если о <!ок„.а, 0(па 1ояп), если ст = 1об, а. Замечание. В оденках вида 0(д(л) 1обь о), где ?с — константа, в основании логарифма предполагается любое постоянное число. При этом переход от одного основания к другому изменяет только константу в О.
Локазатлеаьстео. Пусть и = с", где ?с = 1, 2, 3,.... Тогда, применяя несколько раз (2.3), получаем и л газ '* Ца) ~ (а? ( — ) + Ьо' < о(аЪ( — ) + Ь ~-) ) + Ьп с сз с =Ь +оьн -ь зд,( — ) < < Ьл + Ь ( — ) о~ + а (аЕ ( — ) + Ь ( — ) ) = =Ь Ь ( — ") Ы ® '?,( — ")~ ~~...чЬл +Ьо ( — )+...-~Ьп~( — ) +а Е( — ). Пусть Ы = щах(Ь, ? (1)). Так как ч — — 1, то ц ~<ю'(~~ — +( — ) ~-...+( — ) )+~'= ="( -; (;)' (;-)') Рассмотрим 3 случая: 1) 1об,а < а =э — < 1 =~.? (л) < нп салаг = 0(о"); а 2) 1ок,а > а =э — > 1 =~ =~ Цо) < Иа сооз1 = 0(а ОЯ ") = 0(о 'Я' ) (так как а 'Я " = о'ОЯ'ч); 3) 1оя, а = а =ь а = с' =э Е(л) < Ыл (?с+ 1) = йо (1+ 1оя,о) = = 0(о 1ояо).
Пусть теперь п — любое. Тогда существует такое натуральное й, что сь < п < се+~. Рассмотрим 3 случая, учитывал, что по условию Цо) — неубывающая функция на каждом отрезке [сь + 1, с"~~) (р ниже — некоторая константа); 1) ст > 1об,о =ь Ь(п) < Ь(сз~~) = О(па); 2) ст < 1об,а =з Ь(п) < Ь(сь+з) ьч,а 0( !аз,а).
3) сз = 1о8, а =о Ь(п) < з' (сват) < рс~2п'1об,п = 0(па) 1обп. Теорема доказана. <р("")'=р"(сз) <1 < ( ьат)!аз.а аз,а(сь)~аз,а < < рс1з+О 1о8,(сь ~) < рс (сь) 2~ < 2.3. Алгоритм Карацубы для умножения чисел Если требуется сложить два и-разрздных числа, то можно произвести сложение ав столбик". При этом в каждом разряде нам нужно в зависимости от значений данного разряда в слагаемых и от величины переноса из предыдущего разряда вычислить разряд суммы и величину переноса в слелующий разрял.
Лля одною разряда это требует константного числа операций, а в целом для сложения двух и-разрядных чисел О(п) операций над разрядами. Аналогичную оценку 0(п) можно получить и для сложности вычитащы "в столбик". Только здесь вместо переноса в следующий разряд формируется запрос из следующего разряда. Если лва и-разрядных числа умножать ав столбик", то все разряды первого числа сначала надо умножать на первый разряд второго числа, затем на следующий разряд и т. д. Таким образом число операций над рззрялами будет не менее пз.
Более быстрый (по порядку) алгоритм предложил А. А. Карацуба (8], и именно этот алгоритм считается первым алгоритмом типа "разделяй и властвуй". Лля простоты мы не будем рассматривать адресацию, а будем в качестве алгоритмов рассматривать схемы из функциональных элементов в базисе из всех двухместных булевских операпий и пол сложностью алгоритма понимать число элементов в схеме. В этом случае говорят о битлов отз сложности алгоритма. Теорема 2.5 (Карацуба А. А,).
Дзя умножении двух двоичных и-разрядных чисел суитеспзвуеоз аззоритим с битоеот1 сзожностаью 0(пмз,з) Локоэопзельспзво. Покажем сначала, что алгоритм (схему) для умножения (и + 1)-разрядных двоичных чисел можно получить, используя алгоритм (схему) лля умножения и-разрядных двоичных чисел и дополнительно 0(п) битовых операций. Лействительно, пусть требуется перемножить два (и + 1)-разрядных двоичных числа Х1 = (хо х1 ° ° х!!)2 и 1'1 = (Уо! У1 ° - ° ! У!!)2 Обозна'1изг (х1! т2! ° ° ! х!!)2 = Х и (уь уъ уэ)2 = У. При этом Х1 = хо2" + Х 1'1 = уо2" + У и Х1У1 = хоуо22' + (хоУ + УоХ)2" + ХУ. Поэтому дпя вычисления Х11'1 достаточно испопьзовать умножвтепь М„ддя вычисления ХУ, 2и эпементов для вычисления хоУ и уоХ, 1 эпемевт дпя вычиспения хоуо и 3 сумматора порядка (то есть дпя числа разрядов) не более 2и + 2, так как Х1У1 < 22"+2. Отметим, что числа хоуо к хоУ+уоХ надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
