Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 38
Текст из файла (страница 38)
[НМ30] Покажите, что для в»вода асимптотического разложения г»(т) можно воспользоваться методом исследования асимптотическнх задач при помощи тамма функций вместо формулы суммирования Эйлера (см. (35)). (Это предоставляет едшкюбразный способ аяалвза г»(щ) прн всех к без таких трюков, как введение в рассмотреняе функции д-»(я) = (е-" — Ц/х.) 32. [НМУ5] (Н. Г, де Брейн.) Каково асимптотическое поведение суммы где И(1) — количество делителей числа !? (Таким образом, И(Ц = 1, »((2) = д(3) = 2, 0(4) = 3, И(б) = 2 и т. д. Этот вопрос возникает в связи с анализом алгоритма прохождения дерева из упр.
2.3.1-11.) Найдите значение величины 5„/(~„") до членов порядка 0(п»). 83. (НЛЩ Проанализируйте число проверок рэзрялоя н число обменов, выполняемых при обменной поразрядной сортировке, если нсходнымн дэинммн служат двоичные числа с бесконечной точностью в диапазоне ]О .. 1), каждой разряд которых независимо принимает значение 1 с вероятностью р. (В основном тексте раздела обсуждался лишь случай, когда р = з; применявшиеся методы можно обобщить для провзвольнога р.) Рассмотрите особо случай, когда р = 1/ф = .61803.... $4.
(НМ24] (С. О Райс (Б. О. В(се).) Покажите. что У„можпо записать в виде и! ~Й 1 К, = (-1). 2к1 ус э(з — 1), (х — и) 2* ' — 1' где С вЂ” замкнутая кривая, охватывающая область окало тачек 2,3,..., п. В результате замены С праизвоаьно большой окружностью с центром в начале координат получаем схадшпийся ряд У„= — — +2+ — ~~~ Я(В(п+1, -1+!Ьтп)), (Н 1 — 1)п и 2 )п2 2 )п2 где Ь = 2л/!и 2 и В(п+1, -1+!Ьгп) = Г(я+1)Г( — 1+!Ьш)/Г(п+!Ьт) = и!/ П„" (я-1+(Ьт), ь 68. [88] Покажите, кэк нужно изменить программу Я, чтобы в качестве разделяющего элемента выбиралась медиана нз трех ключей (28), полагая М > 1.
56. (М43] Проанализируйте поведение в среднем параметров, от которых зависит время работм программы (с, если программа изменена тэк, чта онэ выбирает медиану вз трех элементов, как в упр. 55 (см. упр. 29). $.2,3. Сортировка посредствоы выбора Еще одно важное семейство методов сортировки основано на идее многократного выбора. Вероятно, простейшая сортировка посредством выбора сводится к следующему.
!) Найти наименьший ключ, переслать соответствующую запись в область вывода н заменить ключ значением оо (которое по предположению бо.льше любого реального ключа). й) Повторить шаг (!). На этот раз будет выбран ключ, наименьший из оставшихся, так как ранее наименьший ключ был заменем значением оо. ш) Повторять шаг (!) до тех пор, пока не будут выбраны Х записей.
Заметим, что этот метод требует наличия всех исходных элементов до начала сортировки, а элементы вывода порождает последовательно, один за другим. Картина, по существу, противоположна картине, возникающей прн использовании метода вставок, в котором исходные записи поступают последовательно, но вплоть до завершения сортировки об окончательном результате ничего неизвестмо, На шаге (!) требуется выполнить Х-1 сравнений каждый раз, когда выбирается очередная запись.
Также необходимо выделить в памяти отдельную область для накопления результата. Имеется очевидный способ несколько поправить ситуацию: выбранное значение записать в соответствующую окончательную позицию, а запись, которая ее занимала, перенести на место выбранной. Тогда эту позицию не нужно будет рассматривать вновь при последующих выборах и не придется иметь дело с ключом бесконечно больпюй величины.
На этой идее основан наш первый алгоритм сортировки посредством выбора. Рис. 21. Сортировка посредством простого выбора. Алгоритм В (Сортировка посредством простлого выборе). Записи Вы..., Вк перекомпоновываются в пределах того же фрагмента памяти. После завершения сортировки их ключи будут упорядочены: К~ < < Кл. Сортировка базируется на описанном выше методе, если не считать того, что более удобно, оказывается, сначала выбирать наибольший элемент, затем — второй по величине и т.
д. (рис. 21). В1, [Цикл по 7.] Выполнить шаги Е2 и ЗЗ при у' = Ф, Ю вЂ” 1,..., 2. В2. [Найти шах(КО...,К1).] Найти наибольший из ключей К, К. ы, КП пусть зто будет К;, где 1 выбирается как можно ббльшим. ВЗ. [Поменять местами с Вр] Взаимно переставить записи Я, еэ В . (Теперь записи Ву,..., Вк занимают свои окончательные позиции.) 3 В табл. 1 продемонстрирован процесс выполнения этого алгоритма при обработке шестнадцати ключей, выбранных нами для примеров. Элементы, претендующие на то, чтобы быть максимальными во время поиска на шаге Я2, выделены полужирным шрифтам.
Таблица 1 СОРТИРОВКА ПОСРЕДСГВОМ ПРОСТОГО ВЫБОРА 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765703] 503 087 512 061 703 170 897 275 653 426 154 509 612 677 76$]908 503 087 512 061 703 170 76$ 275 653 426 154 509 612 677]897 908 503 067 512 061 793 170 677 275 6$3 426 154 509 612]765 897 908 503 087 512 061 612 170 877 275 6$3 426 154 $69]703 765 897 908 503 087 512 061 612 170 509 275 6$3 426 1$4]677 703 765 897 908 061]087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Соответствующая М12-программа довольно проста.
Программа Я (Сортировка иосредством иросщого выбора). Как и в предыдущих программах из этой главы, записи, находящиеся в ячейках от ТМРУТ+1 до 1ИРОТ+И, сортируются в пределах того же фрагмента памяти по ключу, который занимает полное слово. Значения регистров таковы: гА ив з текущий максимум, Н1 ьз у — 1, г12 ге к (индекс при поиске), г)3 эз з'. предполагается, что х > 2. 01 БТАЕТ ЕИТ1 М-1 ел ~~~ к.
08 2Н ЕИТ2 О, 1 К вЂ” 1 Вг. И К,Д~,Ь 1-1. 03 ЕМТЗ 1,1 Ю вЂ” 1 1~-11 04 Ы$1МРНТ,З А' — 1 гА 4- Кс ОО ЯН СИРА 1ИРУТ,2 А ОО ОСЕ ь+3 А Переход, если К~ > Кю О7 ЕИТЗ О,2 В Иначе — установить зяеМА, ОВ 1.УА 1ИРУТ,З В гА +- Кь ОО УЕС2 1 А А+- А — 1. 1О АР 88 А Повторить, если А > О. 11 ЬУХ 1ИРУТ+1, 1 К вЂ” 1 Я .
Поменять местами с В . 1О ЯТХ 1ИРУТ>3 М вЂ” 1 Кз з- Кз. 18 ЯТА 1ИРУТ+1 в 1 Х вЂ” 1 Вз +- гА. Ц УЕС1 1 К вЂ” 1 16 31Р 28 Ф вЂ” 1 Ю>1>2. $ Время работы этой программы зависит от числа элементов Н, числа сравнений А и числа правосторонних максимумов В. Нетрудно видеть, что независимо от значений исходных ключей А = ~ ) = -Н(Н - 1). Х 1 Следовательно, переменной является только величина В.
Несмотря нэ всю безыс- кусность простого выбора, не так-го легко выполнить точный анализ величины В. В упр. З-б показано, что В = (ппп О, ате (зх + 1)Нм — 2Ю, шах 1Нз/4)). 12) Усовершенствования простого выбора. Существует лн какой-нибудь способ улучшения метода выбора, используемого в алгоритме Б? Возьмем, к примеру, поиск максимума на шаге Б2: возможен ли существенно более быстрый способ нахождения максимума? Ответ на этот вопрос — иепз) Лемма М, В любом алгоритме нахождения максимума среди и элементов, осно- ванном на сравнении пар элементов, необходимо выполнить, по крайней мере, и — 1 сравнений. Дакаэашельсгпео. Если выполнено менее и — 1 сравнений, то найдутся хотя бы два элемента, для которых не было обнаружено ни одного элемента, превосходящего их по величине.
Следовательно, мы так и не узнаем, какой из этих двух элементов больше, а значит, не сможем определить максимум. $ В этом случае особенно интересным оказывается максимальное значение. Стандартное отклонение величины В имеет порядок Нэ/4 1см. упр. 7). Таким образом„среднее время работы программы Б равно 2.5Ф~+ 3(Я+ 1) Ни+ 3.5Ф вЂ” 11 машинных циклов, т. е. данная программа работаег лишь немногим медленнее программы, реализующей метод простых вставок (программа 5.2.1Б).
Интересно сравнить алгоритм Б с сортировкой методом пузырька 1алгоритм 5.2.2В), поскольку метод пузырька можно рассматривать как алгоритм выбора, в котором за один раз иногда выбираетсв более одного элемента. По этой причине при сортировке методом пузырька выполняется меньше сравнений, чем при простом выборе, и она, как может показаться, предпочтительнее. Но в действительности программа 5.2.2В работает более чем вдвое медленнее программы Б! Сортировка методом пузырька проигрывает йз-за того, что выполняется слишком много обменов, в то время как при сортировке посредством простого выбора пересылается очень чало данных.
Таким образом, процесс выбора, в котором выполняется поиск наибольшего элемента, должен включать не менее и — 1 сравнений. Означает ли это, что для всех методов сортировки, основанных на п повторных выборах, число операций неизбежно будет порядка П(пз)? К счастью, лемма М применима только к первол4у шагу выбора; в дальнейшем можно использовать извлеченную ранее информацию.
Например, в упр. 8 и 9 показано, что сравнительно простое изменение алгоритма 8 позволяет наполовину сократить среднее число сравнений. Рассмотрим 16 чисел, представленных в табл. 1. Один из способов сэкономить время при последующих выборах — разбить все числа на четыре группы по четыре числа. Начать можно с определения наибольшего элемента каждой группы, а именно — с ключей 512, 908, 653„765. Тогда наибольший из этих четырех элементов (элемент 908) и будет наибольшим во всей последовательности.
Чтобы получить второй по величине элемент, достаточно просмотреть 512, 653, 765 н остальные три элемента группы, содержащей 908; наибольший из (170, 897, 275) равен 897, и тогда наибольшим среди элементов 512, 897, 653, 765 является 897. Аналогично для того, чтобы получить третий по величине элемент, определяем наибольший нз (170, 275), а затем наибольший из элементов 512, 275, 653„765 н т, д. Каждый выбор, кроме первого, требует не более 6 дополнительных сравнений. В общем случае, если Ф вЂ” точный квадрат, можно разделить массив на ~/Х групп по ~/Х элементов..Чюбой выбор, кроме первого, требует не более чем чу — 2 сравнений внутри группы ранее выбранного элемента плюс ь~Х вЂ” 1 сравнений среди "лидеров групп". Этот метод получил название квадрвши ьимй выбор; общее время его работы составляет порядка 0(Ю~Ю), что существенна лучше, чем Х-". Метод квадратичного выбора впервые был опубликован в работе Е.
Н. Рг(епб, .7АСМ 3 (1956), 152-154. Э. Г. Фрецд указал, что его можно обобщить и получить методы кубической, четвертой и более высоких степеней выбора. Например, метод кубического выбора состоит в том, чтобы разделить массив на чу больших групп, в каждой из которых содержится по ~/Х малых групп по ~/Ю записей. Время работы будет пропорционально №/Ю. Если развить эту идею, можно прийти к тому, что Френд назвал "выбор и-й степени", базирующийся на структуре бинарного дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
