Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 52
Текст из файла (страница 52)
Всякий раз, когдаэто оказывается возможным, мы выбираем граф с меиыпей эффективностью и добавляем его к нашему множеству, если только он не является изоморфным одному из уже включенных в множество графов. Если оба полученных графа имеют одинаковую эффективность, то произвольным образом выбирается один нз них.
Граф можно приравнять к ,двойственному ему графу (т. е. полученному в результате обращения отношения порядка) прн рассмотрении вопроса о добавлении сравнений как к С' 6! 4!иа1(С"), так и к С' !9 С". Несколько графов, полученных таким способом, изображены на рис. 36, на котором приведены также значения их эффективности, Прежде чем этот процесс завершился, при помощи компьютера было построено ровно 1649 графов. Поскольку граф не был получен, можно сделать вывод о том, что 8(12) > 29. Весьма правдоподобно, что и для доказательства неравенства Я(22) > 70 можно выполнить аналогичный эксперимент за вполне разумное время, поскольку 22!/270 ю 0.952 — это чрезвычайно высокая эффективность для сортировки за 70 шагов.
(Из 1 649 найденных графов с 12 или менее вершинами всего 91 имеет столь высокую эффективность.) Промежуточные результаты дают веские основании предпатожить, что Я(13) = 33 и, следовательно, сортировка посредством вставок и слияния не оптимальна при Оз г( г Сг ° 1 ',з С ч~~ Я аг Я аз ~, Ц Зг Й6 зм эм 610 гзг ~м згг 0м 1 б)3~ ~~ ~~» 1 ~14 ~~Я 1 б1г ~» 1 ~ы ~~~~э 64 м»ь~~, ~В~ 01з гк»~» зг Сг|з з~~) ззг ~ге ~~~~~~м зА Огг .к.'..л „ и Рис. 36.
Некоторые графы н значения их эффективности, подученные на начальной стадии длинного доказательства неравенства Я12) > 29. п = 13. Наверкяка можно доказать, что о(16) < Г(16), поскольку Г(16) - — зто как раз такое число сравнений, какое требуется, чтобы сначала рассортировать 10 элементов за 5(10) шагов, а затем посредством бинарных вставок вставить по одному остальные 6 элементов. Непременно должен существовать более хороший способ! Но в настоящее время вариант с наименьшим значением, в котором точно известно, что Г(п) неоптимально, — зто и = 47: после сорти1ювки 5 и 42 элементов, где требуется Е(5) + Е(42) = 178 сравнений, мы можем слить результаты, на что потребуется еще 22 сравнения, используя метод, предложенный в работе Л. БсЬпйе МоЬпи16, ТЬеоге1- гса) Ссапр.
Ясй 14 (1931), 19-37; этот результат превышает значение Р(47) = 201. (В работе С)епп К. МапасЬег, .ТАСМ 26 (1979), 441-456, показано, что существует бесконечно много значений п, начиная с и = 189, для которых о(п) < Г(п).) 2+3+3+3+3+2 з ц обцгем случае среднее число сравнений для метода сортировки есть длина внешнего орши дерева, деленнан на пй (Напомним, что длина внешнего пути -- зто сумма всех расстояний от корня до каждого из внешних узлов; см. раздел 2.3.4.5.) Из анализа в разделе 2.3.4.5 следует, что минимальная длина внешнего пути достигается на таком бинарном дереве с Ф внешними узлами, у которого имеется 2г — Х Среднее число сравнений.
До сих пор мы рассматривали процедуры, наилучшие в том смысле, что они не плохи в наихудшем случае; мы искали 'миннмаксные" процедуры, минимизирующие макспмвльное число сравнений. Поищем теперь "мини- средние" процедуры, минимизирующие среднее число сравнений в предположении, что входные данные случайны, т. е. все перестановки равновероятны. Рассмотрим еше раз изображенное на рис. 34 представление процедуры сортировки в зиле дерева. Среднее число сравнений по всем перестановкам длн этого дерева равно ол о.о о ~ оз о,з ол о.а од ол оа ол по Рис. 37.
Функция ! +д — 2~. внешних узлов на уровне д — 1 и 2Ж вЂ” 2г на уровне д, где о = !!8Х1. (Корень находится на нулевом уровне.) Таким образом, минимальная длина внешнего пути равна (34) (д — 1)(2Я вЂ” Х) + д(2Х вЂ” 2Я) = (д+ 1)Ю вЂ” 2Я. Имеется еще один интересный способ охарактеризовать минимальную длину пути: расширенное бинарное дерево имеет минимальную длину внешнего путп тогда и только тогда, когда сушестиуег такое число 1, что все внешние узлы находятся на уровнях ! и 1+ 1 (см. упр. 20). Если положить о = 18Х + д, где 0 < д < 1, то формула минимальной длины внешнего пути примет вид Х(18 Х + 1+ д — 2а).
(35) График функции 1 ч. д — 2а изображен на рис. 37; при 0 < 9 < 1 она принимает положительные, ио очень малые значения, не превышающие 1 — (1+ 1п!п2)/!в 2 = 0.08607 13320 55934+, (36) Таким образом, минимальная возможная средняя длина пути, которая получается в результате деления (35) на 7т, не может быть меньше 18 Ф н болыпе 18 %+ 0.0861.
(Этот результат впервые получил Э. Глисон (А. О!еааоп) в неопубликованной заметке 1956 года.) Если теперь положим Х = и!, то получим нижнюю оценку среднего числа сравнений но всем схемам сортировки. Оценка асимптотически приближается к 18 п! + 0(1) = и )8 и — и/ ! п 2 + 0(1о8 и).
(37) Пусть г"(и) -- среднее число сравнений, выполняемых алгоритмом сортировки посредством вставок и слияния; имеем п=1 2 3 4 5 6 7 8 Нижняя граница (34) = 0 2 16 112 832 6896 62368 619904 и! Р(п) = 0 2 16 112 832 6912 62784 623232 Итак, сортировка посредством вставок и слияния оптимальна в обоих смыслах при п < 5, однако при и = 6 такой метод в среднем требует 6912/720 = 9.6 сравнений вместо возможных согласно нижней оценке 6896/720 = 9.577777... сравнений. Немного поразмыслив, нетрудно понять. почему это так: некоторые "удачные" перестановки шести элементов сортируются методом вставок и слияний всего за восемь сравнений, и тогда дерево сравнений имеет внешние узлы на трех, а не на двух уровнях. Изза этого увеличивается суммарная длина пути.
В упр. 24 показано, что можно построить процедуру сортировки шести элементов, требующую всегда девять или десять сравнений; следовательно, этот метод превосходит метод вставок и слияний в среднем и не хуже него в худшем случае. В работе У. Сбзаг), Тпешв (Вшк. о( Рапз, 1968), раде 37, показано, что при и = 7 не существует метода сортировки, при котором достигалась бы нижняя граница длины внешнего пути (62363). (Используя результат упр.
22, этот факт можнодоказать самостоятельно.) С другой стороны, в указанной работе построены процедуры, для которых достигается нижняя граница (34) при и = 9 или 10. Вообще же, задачу минимизации среднего числа сравнений решить гораздо сложнее, чем найти л'(и), Вполне даже возможно, что прн некоторых и все погоды, минимизирующие среднее число сравнений, в худшем случае требуют более 5(п) сравнений. УПРАЖНЕНИЯ 1. [20) Нарисуйте деревья сравнений для сортировки четырех элементов методами (а) бинарных вставок; (Ь) простого двухпутевого слияния. Каковы длины внешних путей для этих деревьев? 2.
[М24) Докажите, что В(п) < Ь(п), и найдите все значения я, при которых имеет место равенство. 3, [М22[ Если допускаются равные ключи, то при сортировке трех элементов возможны 13 исходов: % =Кэ=Кз, Кз = Аэ < Кэ, Кз<К~ жК», Кэ<К$<Кз, Кэ<КЗ К~=Кэ<Кз, К~=Кз<Км К~ <Кэ=Кэ, Кэ <К~ =Кз, К1<кэ<кз, К1<кз<Км <Км Кэ<К~<Км Кэ<Кэ<Кэ. Обозначим через Р число возможных исходов при сортировке н элементов, если допускаются равные ключи, так что (Ро,РмРз, Рз,Рэ,Рм ) = (1, 1, 3, 13, 75, 541,...). Докажите, что производящая функция Р(з) = 2 „>эР„з"/н! равна 1/(2 — е*).
Указание. Покажите, что Р. Х ~©Р.-, Прнп>б. з>о 4. [НМ27) (О. А. Гросс (О. А. Стоге).) Найдите асимптотическое выражение для чисел Р„нз упр. 3 при и -+ ао. [Указание. Рассмотрите разложение сос г иа элементарные дроби.) 5. [10) Если допускаются равные ключи, то каждое сравнение может иметь не два, а три результата; К, < К„К; = К„К„> К,, В этом общем случае алгоритмы сортировки можно представлять в виде расширенных шеряарнмз деревьев, в которых каждый внутренний узел 1: У имеет три поддерева (левое, среднее и правое), соответствующие трем возможным исходам сравнении. Нарисуйте расширенное тернарное дерево, определяющее алгоритм сортировки для и = 3, если допускаются равные ключи. В вашем дереве должно быть 13 внешних узлов, соответствующих 13 возможным исходам, перечисленным в упр.
3. б. [М22[ Пусть 2 (и) — минимальное число сравнений, необходимое для сортировки и элементов н выявления всех равенств между ключами, если каждое сравнение имеет три возможных результата. как в упр. 5. Нетрудно обобщить "теоретико-информационные." аргументы, приведенные в тексте раздела, и показать, что 2'(и) > [(обэ Р ), где Р функция, проанализированная в упр, 3 и 4; докажите„что на самом деле 2'(и) = 2(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
