1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 15
Текст из файла (страница 15)
Тогда описанный выше алгоритм нашел бы наибольший н наименьший элементы в каждой нз двух половин с помощью рекурсии. Наибольший н наименьший элементы множества 5 можно было бы определить, произведя еще два сравнения — нанбольшнх элементов в 5, н 5, н наименьших элементов в ннх. Сформулируем этот алгоритм более точно. Алгоритм 2.3. Нахождение нанбольшего н нанменьшего элементов множества Вход. Множество 5 нз и элементов, где и — степень числа 2, и 2. Выход. Наибольший н наименьший элементы множества 5. Метод. К множеству 5 применяется рекурсивная процедура МАХМ1(ь).
Она имеет один аргумент '), представляющий собой множество 5, такое, что !Щ=2з прн некотором й)1, н вырабатывает пару (а, Ь), где а — наибольший н Ь вЂ” нанменьшнй элементы в 5. Процедура МАХМ1!ч( приведена на рнс. 2.12. П Заметим, что сравнения элементов множества 5 происходят только на шаге 3, где сравниваются два элемента множества 5, нз которых оно состоит, н на шаге 7, где сравниваются шах! с шах2 н ппп! с ппп2. Пусть Т(а) — число сравнений элементов множества 5, которые надо произвести в процедуре МАХМ1Р(, чтобы найтн наибольший н наименьший элементы и-элементного множества. Ясно, что Т(2)=1. Если п)2, то Т(п) — общее число сравнений, произведенных в двух вызовах процедуры МАХМ1(ь( (строкн б н б), работающей на множествах размера л/2, н еще два сравнения В ') Так как здесь подсчятывакпся только сравиеиия, способ прохождения аргументов яесушествея.
Однако, если множество 3 предсгавлеио массивом, можно оргаиизовать аффективный вызов МАХМ11ч, поставив указатели яа первый я последний злемеиты подмножества 8, состояшего из последовательиых компокеят этого массива. ЧЬ на. разделяя и влдствнн ргоседцге МАХМ1Ы(5): 1. !! ()5(=2 !Ьеп Ьей! и 2. пусть 5=(а, Ь); 3. ге!пгп (МАХ(а, Ь), М1И(а, Ь)) епд е!зе Ьей)п 4. разбить 5 на два равных подмножества 5, и 5,; б.
(шах1, ш!п1) — МАХМ1Ь)(5,); б, (шах2, ш!п2) — МАХМ1Ь!(5,); 7. ге!пгп (МАХ(шах1, шах2), М1Ь)(ш!п1, ш!п2)) епд Рис. 2.!2. Процедура дня нахождения МАХ и М11я. строке 7. Таким образом„ 1 при п=2, Т(л) = 2Т (и/2) = 2 при и > 2. (2.2) т. е. она удовлетворяет (2.2) при л=2гп. Таким образом, индукцией по н доказано, что Т (л)=аlяа — 2 удовлетворяет (2.2), если л есть степень числа 2. Можно показать, что для одновременного нахождения наибольшего и наименьшего элементов п-элементного множества надо сделать не менее еlяц — 2 сравнений его элементов. Следовательно, алгоритм 2.3 оптимален в смысле числа сравнений между элементами из 5, когда а есть степень числа 2. В предыдущем примере прием "разделяй и властвуй" позволил уменьшить количество сравнений лишь в фиксированное число раз.
В следующем примере мы с помощью этого приема уменьшим даже порядок роста сложности алгоритма. Рассмотрим умножение двух а-разрядных двоичных чисел. Традиционный метод требует 0(п') битовых операций. В методе, изло- гг Решением рекуррентных уравнений (2.2) служит функция Т(п)=Чан — 2. Легко проверить, что эта функция удовлетворяет (2.2) при п=2, и если она удовлетворяет (2.2) прн л=лт, где гл)~, Т (2ш) = 2 ~ — 2 ) + 2 = — (2л!) — 2, /зт т 3 ГЛ. 2. РАЗРАБОТКА ЗФФЕКТИВНЫХ АЛГОРИТМОВ Рнс. 233. Разбиение цепочек, представленных в виде двоичных чисел.
(2.4) 79 женном ниже, достаточно уже порядка л"а', т. е. примерно л'" битовых операций '). Пусть х и у — два л-разрядных двоичных числа. Снова будем считать для простоты, что л есть степень числа 2. Разобьем х и у на две равные части, как показано на рнс. 2.13. Если рассматривать каждую из этих частей как (л/2)-разрядное число, то можно предста- вить произведение чисел х и у в виде ху=(а2"12+Ь) (с2юэ+21) = = ас2" + (аг(+ Ьс) 2юх + Ы, (2.3) Равенство (2.3) дает способ вычисления произведения х и у с помощью четырех умножений (п/2)-разрядных чисел и нескольких сложений н сдвигов (умножений на степень числа 2).
Произведение г чисел х и у также можно вычислить по следующей программе: Ьей(п и (а+Ь)и(с+2()1 и -анс; гв Ьег(; г — о н 2" + (и — о — гс) и 2" м + гв епй На время забудем, что из-за переноса а+Ь и с+2( могут иметь л/2+1 разрядов, н предположим, что они состоят лишь из и/2 раз- рядов. Наша схема для умножения двух и-разрядных чисел требует только трех умножений (л/2)-разрядных чисел и нескольких сло- жений н сдвигов. Для вычисления произведений и, о и гс можно применять эту программу рекурсивно. Сложения и сдвиги занимают ОБ(п) времени.
Следовательно, временная сложность умножения двух л-разрядных чисел ограничена сверху функцией ~Ь при и=1, Т(л) = (2.5) ( ЗТ (и/2)+ Ьп при и > 1, где Ь вЂ” постоянная, отражающая сложение и сдвиги в выражениях, входящих в (2.4). Решение рекуррентных уравнений (2.5) ограни- чено сверху фуннцией Зйи1он эимЗЬпг ее . '1 Напомним, что, если не оговорено противное, все логарифмы в этой книге берутся по основанию 2, З.е.
РАЗДЕЛЯЙ И ВЛАСТВУЙ На самом деле можно показать, что в (2.5) Т (и) Зйп1он з 2йп Доказательство проведем индукцией по и, где и — степень числа 2. Базис, т. е. случай л=1, тривиален. Если функция Т(л) =Зйлни' — 2/гп удовлетворяет (2,5) при п=пз, то Т(2пз) =ЗТ(т)+2ЬД= = 3[ЗЬп~оя з 2йпз).+2Ьп Зиь (2пз) ~он з 2Ь (2зл) так что она удовлетворяет (2.5) и при л=2лз. Отсюда следует, что Т (л)(Зйпмз '. Заметим, что попытка использовать в индукции Зйпн'и * вместо Зйп"' ' — 2йл не проходит. Для завершения описания алгоритма умножения мы должны учесть, что числа а+Ь и с+з(, вообще говоря, имеют л/2+! разрядов, и поэтому произведение (а+Ь)(с+з() нельзя вычислить непосредственным рекурсивным применением нашего алгоритма к задаче размера л72. Вместо этого надо записать а+Ь в виде а,2""+Ь„ где а,=О или 1. Аналогично запишем с+з( в виде с,2з1з+з(з. Тогда произведение (а+Ь)(с+с() можно представить в виде а,сз2" + (азз(, + Ь,с,) 2о~з + Ь,з(,.
(2.6) Слагаемое Ь,з(з вычисляется с помощью рекурсивного применения нашего алгоритма умножения к задаче размера п72. Остальные умножения в (2.6) можно сделать за время ОВ(п), поскольку они содержат в качестве одного из аргументов либо единственный бит а, или с„либо степень числа 2.
Пример 2.6. Этот асимптотически быстрый алгоритм умножения целых чисел можно применять не только к двоичным, но и к десятичным числам. Проиллюстрируем это на примере: х = 3141 а = 31 с=59 у 5927 Ь = 41 з(= 27 а+Ь=72 с+з(=86 и = (а+ Ь) (с+ з() = 72 х 86 = 6192 о=ас=31х59 = 1829 зс=Ьз(=4! х27=1107 хр =! 8290000') + (6192 — ! 829 — 1107) х 100+ 1!07=18616707 С) Заметим, что алгоритм, основанный на (2.4), заменял одно умножение тремя сложениями и вычитанием (ср. с (2.3)). Почему такая замена приводит к асимптотической эффективности, можно интуи- ') Число о следует едяинуть нз четыре десятичных рззрядз, з и — о — оз — нз днз. 79 Гл. ь РАБРАБОткА ЗФФБктиВных АлгоРитмов тивно объяснить тем, что умножение выполнить труднее, чем сло- жение, и для достаточно больших и любое фиксированное число и- разрядных сложений требует меньше времени, чем и-разрядное ум- ножение, независимо от того, какой из (известных) алгоритмов при- меняется, Вначале кажется, что уменьшение числа (и/2)-разрядных произведений с четырех до трех может уменьшить общее время в лучшем случае на 25%.
Однако соотношения (2.4) применяются рекурсивно для вычисления (п/2)-разрядных, (сй4)-разрядных н т. д. произведений. Эти 25-процентные уменьшения объедииякпся и дают в результате асимптотическое улучшение временной слож- ности. Временная сложность процедуры определяется числом и разме- ром подзадач и в меньшей степени работой, необходимой для раз- биения данной задачи на подзадачи.
Так как рекуррентные уравне- ния вида (2.2) и (2.5) часто возникают при анализе рекурсивных ал- горитмов типа „разделяй и властвуй", рассмотрим решение таких уравнений в общем виде. Теорема 2.1. Пусть а, Ь и с — неотрицательные поипоянные. Решение рекуррентных ураенени й ~ь при =п1, Т (и) = ( аТ (псе) + Ьп при и > 1, еде п — степень числа с, имеет еид, 0(п), если а(с, Т(п) = 0(п1ойп), если а=с, 0 (имя '), если а > с. Д о к а з а т е л ь о т в о. Если п — степень числа е, то ье,л Т(п)=Ьп л.", г', где с=а(с. с о Если а«с, то ч ~ с сходится и, следовательно, Т(п)=0(п). 2 Если а=с, то каждым членом этого ряда будет 1, а всего в нем 0(!оц и) членов. Поэтому Т(п)=0(п 1оя и).
Наконец, если а)с, то А»ас А 2+ СОБР Л Ьп ~ч» гс=Ьп » Ю что составляет 0(асье2") или 0(п'""). 1..) Из теоремы 2.1 вытекает, что разбиение задачи размера и (за линейное время) на две подзадачи размера и/2 дает алгоритм сложности 0(п 1оя и). Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка и"е', и'- или и" соответственно. 2.7. БАЛАНСИРОВКА С другой стороны, разбиение задачи на 4 подзадачи размера л/4 дает алгоритм сложности 0(п 1оя и), а на 9 и 16 — порядка л"з* и л' соответственно.
Поэтому асимптотически более быстрый алгоритм умножения целых чисел можно было бы получить, если бы удалось так разбить исходные целые числа на 4 части, чтобы суметь выразить исходное умножение через 8 или менее меньших умножений. Другой тип рекуррентных соотношений возникает в случае, когда работа по разбиению задачи не пропорциональна ее размеру. Некоторые типы рекуррентных соотношений вынесены в упражнения. Если п не является степенью числа с, то обычно можно вложить задачу размера л в задачу размера и', где л' — наименьшая степень числа с, большая или равная и.
Поэтому порядки роста, указанные в теореме 2.1, сохраняются для любого а. На практике часто можно разработать рекурсивные алгоритмы, разбивающие задачи произвольного размера нас равных частей, где с велико, насколько возможно. Зтн алгоритмы, как правило, эффективнее (на постоянный множитель) тех, которые получаются путем представления размера входа в виде ближайшей сверху степени числа с. 2.7. ВАЛАНСИРОВКА В обоих наших примерах на технику "разделяй и властвуй" задача разбивалась на подзадачи равных размеров. Зто ие было случайностью.
Поддержание равновесия — основной руководящий принцип при разработке хорошего алгоритма. Для иллюстрации этого принципа мы приведем пример из сортировки и сопоставим эффекты ат разбиения задачи на подзадачи неравных размеров и на подзадачи равных размеров. Из этого примера не следует заключать, что "разделяй и властвуй" — единственная техника, в которой полезна балансировка. В гл. 4 приводится несколько примеров, в которых эффективные алгоритмы получаются в результате балансировки размеров поддеревьев или весов двух операций. Рассмотрим задачу расположения целых чисел в порядке неубывания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
