Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 90
Текст из файла (страница 90)
Агпысгопб) ]ем. Г Я. Расея! 3399383 (1965)]. Пратт предполагает, что эти исходные последовательности представляют наихудший случай из возможных.] 64. При быстрой сортировке каждый ключ Кэ,, Лл сравнивается с Км пусть А = (! ] Л, < К~), В = (3 ] Л; > К~). Далее метод быстрой сортировки независимо применяется к А и В. Все сравнения К„: Кэ для ! в А н У в В запрещаются как при быстрой сортировке, так и в алгоритме ограниченной однородной сортировки, но никакие другие сравнения не запрещаются в алгоритме неограниченной однородной сортировки.
В этом случае мы могли бы еще больше ограничить алгоритм, опуская случаи 1 н 2 так, что к 0 добавляются дуги, только если явно выполняются сравнения, и рассматривая при проверке избыточности лишь пути длиной 2. Другой способ решения этой задачи заключается в том, чтобы рассмотреть эквивалентный алгоритм вставки в дерево (рвэдел 6.2.2), который выполняет те же сравнения, что и однородный алгоритм, и в том же порядке.
65. Вероятность того, что Л, сравнивается с Кьл — зто вероятность того, что с, других звдънных ключей не лежат между Кеч и Кь,; это, в свою очередь, есть вероятность того, что два числа, случайно выбранные из (1,2,...,с,+2), окажутся последовательными, а именно (Ь) Первы» и-1 значений с; равны нулю; затем идут (и — 2) единиц„(п-3) двоек и т. д.; среднее значение, следовательно, равно 2) 'ь",(и-в)/(к+1) = 2 2 ",((и+1)/(и+1) — 1) = 2(и+1)(Н ьь — 1) - 2н. (с) Раздвоенность, характерная для слияния, приводит к тому, что алгоритм ограниченной однородной сортировки совпадает с алгоритмом однорцлной сорткровки для этой последовательности.
Пары, содержащие вершину )т', имеют значения с, равные соответственно О, 1,..., Ж-2; поэтому среднее число сравнений точно такое же, как и при быстрой сортировке. 66. Нет. Когда )г' = 5, никакая последовательность пар, оканчивающаяся на (1, 5)(1,2) (2, З)(3, 4)(4, 5), не будет требовать 10 сравнений. [Интересная проблема для исследования: найти для любого коне'пюго Х однородный метод сортировки, наилучший из возможных в наихудшем случае.] 67.
Гил Калан (С!! Ка1ш) неофициально сообщил о найденном доказательстве минимальности для ограниченного случая. Он использовал метод, изложенный в его же статье в Сгарйэ алд Сотб!ла1ог1сэ 1 (1985), 65-79; однако само доказательство не опубликовано. 68. Эа каждый проход элемент может потерять не более одной инверсии, поэтому минимальное число проходов не мохсет быть меньше максимального числа инверсий любого элемента исходной перестановки. При стратегии метода пузырька эта граница достигается, так как каждый проход уменьшает на единшгу число инверсий каждого элемента, обладающего инверсиями (см, упр, 5.2.2-1). Мог бы потребоваться дополнительный проход, чтобы определить, закончена ли сортировка, но формулировка этого упражнения позволяет нам ие учитывать соображения таащ о рода.
Возможно, наше несчастье в том, что первая теорема в изучении вычислительной сложности автоматов усгвновила 'оптимальность" метода сортировки, который так плох с точки зрения его щюграммной реализации! Положение аналогично истории с датчиками случайных чисел, когда было сделано несколько шагов назад, как только датчики, "оптим!ьчьные" с одной частной точки зрения, были рекомендованы для общего использования, (См. комментарии к выражению З.З.З-(39).) Отсюда мораль: рассуждения об оптимальности зачастую сильно зависят от принятого уровня абстракции модели; всякие результаты, даже очень интересные, требуют осмотрительности при нх практическом применении. [,Демут далее рассмотрел более общую машину с г регистрами (это ускорвет работу в г раз) и устройство, аналогпчное машине Тьюринга, в котором направление движения может по желанию переключаться. Он обнаружил, что этот вид машин способен выполнять простые вставки и шейкер-сортировку; но любая такая машина с одним регистром должна в среднем совершить не менее -„'(Х вЂ” Ж) шагов, так как каждый шаг уменьшает общее число инверсий не более чем на единицу, Наконец, он рассмотрел г-регистровые машины с произвольным доступом н вопрос сортировки с минимальным числом сравнений.
Эта часть его тезисов была опубликована в 1ЕЕЕ Тгапяасйолэ С-34 (1985), 296-310.[ РАЗДЕЛ 5.4 1. Можно обойтись без фазы внутренней сортировки, но при этом работа значительно замедлится, так как возрастет число считываний каждой части данных нз внешней памяти н записи в иее. 2. Серии распределяются как в (1), затем на ленту 3 записываются Е1 . - Еэаеомю; Еэоооем пээоаооо; /глооеоо! . /гэоэаооо. После перемотки всех лент в результате выполнения "однопутевого" слияния на ленты Т! и Тэ будет помепшно соответственно содержиыое Тэ и Т4 в (2). Затем Тл и Тг сливаются на Тэ, информация копируется и сливается еще раз; в итоге ил1еем пять проходов. В общем случае эта процедура аналогична четырехленточному сбалансированному слиянию, но выполняется копирование между дюбыми двумя слияниями, что приводит, таким образом, к удвоенному числу проходов ллинус один.
1 Л) ~М Л! (Ч 1ч Г, В /Ъ~Г- Р~ — "Лл мощность слияния". При Т = 2Р эффективная мощность равна Р, при Т = 2Р— 1 она равна л/Р(Р— 1) = Р— -' — -'„Р ' + О(Р э), что несколько меньше, чем -'Т. 4. -'Т. Если Т нечетно, а Р должно быть целым, то как [Т/2), так и [Т/2) дщот одинаковое максимальное значение, В соответствии с упр. 3 лучше иметь Р > Т вЂ” Р, поэтому для сбалансированного слияния мы выбираем Р = [Т/2).
РАЗДЕЛ $,4,1 303~~~ 1. 087 134 170 426 426 / 426 653 оо ).612 оо 2. путь (бб!)'— -(э!2) —.Созт) — -С!64) — Сбб!) был заменен путем б!2 б!2 5!2 !64 037 . (По существу, мы выполняем сортировку методом пузырька от нюкней части к вершине дерева вдоль это!о пути.) 3. ааб уовгвсоге овг аегев уеаге/ або Ьгоабйс уасьегв тегсЬ ов сала/ а сопселгеб совсгпевс лл 11Ьвгсу вас!оп аея сье со/ ааб бей!сагиб иев ргорое1с1еа сбас/ а11 аге сгеасеб ецва1.
4. (Эта задача несколько двусмысленна; здесь мы не очищаем внутреншою память, пока дополнительный буфер не будет близок к переполнению.) ал4 Тоагвсоге ои оаг затеи СЬАэ увага/ або Ьгоэййс сопсАаваС ТаСЬеге ТогсИ ха 11Ьегсу ааСАоа аея со/ а аа4 соасехэе4 4е41сасе4 иеп ргороэАС(оп сйаС СИе/ а11 агв сгеасе4 ециа1. б. Неверно: полное двоичное дореэо с Р узлами определено для ясех Р > 1, 6.
Вставить "'если Т = ЬОС(Х(О]), то переход к шагу В2; в противном случае" э начало шага Йб и исключить аналогичную фразу из шага ВТ. Т. Алгоритм ничего не выдает, КИАК остается равным О. 6. Если бы любой из периых Р реальных ключей оказался равным оо„то запись п(юпэла бы. Чтобы избежать этого, мы можем ввести переключатель, установив его так, чтобы на шаге В4 сравнение с ЬАЕТКЕТ первоначально не выполнилось. Затем, когда впервые окажется КО ф 0 на шаге ВЗ, переключатель изменяет саое состояние таким образом, что далее не выполншотся шаг В1 и анализ КО на шаге ВЗ. 9. Предположим, например, что текущая серия — восходящая, тогда как следующая должна быть нисходящей.
В этом случае алгоритм В будет работать правильно при одном изменении: на шаге Вб, если КИ(Т) = КО > ЕС, следует изменить на противоположный знак сраэнеиня КЕТПОЕЕК(Т)) с КЕТ(О). Когда КС меняется, проверки ключей на шагах В4 и Вб должны изменяться соответствующим образом. 10. Пусть у ез ЬОС(Х(у]) . Алгоритм В обеспечивает выполнение следуюп(их условий при достижении шаха ВЗ, если заранее установлено ЬОЕЕК(.0) +- Ц и ЕИ( О) .— ЕО, Значения ЬОБЕК( О), ..., ЬОЯЕК( (Р— 1)) представляют собой перестановку множества ( О, 1, ...
> .(Р— 1)); существует перестановка указателей (ЬОЕЕЕ( у) ] КИ(.у) = О), которая соответствует текущей турнирной сетке. Другими слоэамн, если КИ(у) равно нулю, величина КЕТ(1.08ЕЕ(,)) ) не имеет значения; можно переставить "проигравших" друг с другом. После Р шагов все КИ( у) будут отличны от нуля. Таким образом, дерево будет сформировано полностью.
(Огэст на указание -- "да".) Любители строгости формулировок могут возразить, что алгоритм срааниваег значения КЕТ, которые еще не иницнализированы. Если вас это тоже смущает, можете избежать такой ситуации, установив на шаге В.1 все КЕТ равными О. 11. Верно. (Оба ключа принадлежат одной подпоследовательности из доказательства теоремы К.) 13. После завершения первой серии в памяти обычно остаются ключи, меныпне среднего, так как именно из-за своей малой величины оэш не попали в первую серию. Поэтому во иторую серию выэодится большее количество меньших ключей. 14. Предположим, что снег эиезапно прекрапшется, когда снегоочиститель находится е случайной точке и, О < и < 1 (после достижения установившегося состояния).
Тогда предпоследняя серия содержит (1+ 2 и -н~) Р записей, а последняя — и~Р. Интегрирование по 4и дает среднее количество записей (2- з] Р в предпоследней серии и -'Р— э последней. 15. Неверно, Последняя серия может быть сколь угодно длинной, но только и сравнительно редком случае, когда э момент исчерпания исходных данных эсе записи э памяти принадлежат одной серии. 16. Тогда и только тогда, когда каждый элемент имеет меныпе Р инеерспй. (См. разделы 5.1.1 н 5.4.8.) Рассматривая таблицу инверсий, находим вероятность, которая равна 1 прн А( < Р н Р Р)/Х! при А( > Р.
(Практически, однако, сортировка за один проход -— ке такое уж редкое явление, поскольку люди часто в целях предосторожности склонны сортировать файл при малейшем подозрении, что порядок э ием нарушен.) 17. Ровно (Х/Р) серий. Все серии, кроме последней, имеют длину Р. (Нликудпшй случай.) 18. При втором проходе ничего не изменится, так как можно показать, что )г-я запись какой-либо серии меньше„чем, по крайней мере, Р+ 1 — и записей предыдущей серии для 1 < ь' < Р. (Однако вряд ли существует простой способ охарактеризовать результат Р'- путевого выбора с замещением, примененного после Р-путевого выбора с замещением при Р' > Р.) 19. Так же, как прн вьпюде (2), убеждаемся, что й(х, 1) г(х = КЕМ, где на этот рэз й(х, 1) = 1+ К1 для всех х и Р = Ы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
