Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 28
Текст из файла (страница 28)
Более подробно асимптотическое поведение величины А„при М = Ф/а обсуждается в упр. 40.) Рассматривая совместно (17) и (18), можно получить общее время выполнения программы М при фиксированном М н Х -~ оо: ш)п 31Ф+ М+ 2, ате 1.75Фз/М+ 31Н вЂ” ЗМНи+ ЗМ1пМ+4М вЂ” Зд — 1.75Н/М+ 2, шах 3.50Ф~+ 24.5Н+ 4М+ 2. (19) Заметим, что е«ли М не слишком велико, то среднее время выполнения сокращается в М раз. При М = 10 сортировка будет осуществляться примерно в 10 рвз быстрее, чем при М = 1. Однако максимальное время выполнения гораздо больше среднего.
Таким образом, подтверждается важность выполнения условия равномерности распределения ключей, так как наихудший случай имеет место, когда все ключи попадают в один список, Если положить М = Ж, то среднее время выполнения будет составлять примерно 34.36Н машинных циклов. При М = 1Ф оно несколько больше, приблизительно 12 34.52Ю машинных циклов, а прн М ж 78Ф вЂ” приблизительно 48.04Н. (Заметим, что 10Ф машинных циклов 81Х при атом тратятсн на одну лишь команду умножения!) Дополнительные затраты на сопровождающую программу из упр. 35, которая связывает воедино все М списков, увеличивают время выполнения приблизительно до 44.99Ф, 41.95Н и 52.74% соответственно вариантам значения М. Таким образом, получен метод сортировки с временем работы порядка Н пря условии, что ключи доволыю равномерно распределены в области возможных значений.
Пути дальнейшего совершенствования метода вставок в несколько списков обсуждаютсл ниже, в разделе 5.2.5. УПРАЖНЕНИЯ 1. [10) Является лн алгоритм 8 алгоритмом "устойчивой" сортировки? 2. [11) Будет ли алгоритм 8 правильно сортировать числа, если на шаге 83 отношение К > К; заменить отношением К > К;? 3. [30) Является ли программа 8 самой короткой программой сортировки для машины й11, нлн можно написать еще более короткую программу, которая давала бы тот же результат? 4. [Мйй) Найдите минимальное н максимальное время ныполиения программы 8 как функцию от Х б.
[М27) Найдите производящую функцию уя(г) = 2 гйерлггг для общего времени выполнения программы 8, где рлг — вероятность того, что на выполнение программы 8 уйдет ровно?г машинных циклов при заданной исходной случайной перестановке множества (1,2,...,К1. Вычислите также стандартное отклонение времени выполнения лля данного значения Ф. 6. [20) Для метода двухпутевых вставок,проиллюстрировашюго в табл. 2, по-видимому, необходимо, помимо области ввода, содержащей г( записей, иметь область вывода, в которой может храниться 2Ф+ 1 записей.
Покажите, что можно выполнять двухпутевме вставки, имея в памяти как для ввода, так и для вывода пространство, достаточное для хранения всего 2М + 1 записей. 7. [М20) Пусть а~ аг,. а„— случайная перестановка множества (1,2,, и). Каково среднее значение величины [а, — 1[+ [аг — 2[+ - + [а„— и[? (Оно раию произведению и и среднего чистого расстояния, на которое перемещается запись в процессе сортировки.) 8. [10) Является лн алгоритм П алгоритмом "устойчивой"' сортировки? 9. [20) Какие значения А и В и какое общее время работы программы О соответствуют табл. 3 н 4? Проаналп'е руйте достоинства метода Шелла по сравнению с методом простых вставок в атом случае.
ь 10. [22) В случае, когда Кг > К ь, на шаге ПЗ алгоритм П предписывает выполнение множества ненужных действий. Покажите, как можно изменить программу П, чтобы избежать зтих избыточных вычислений, и проанализируйте преимущества такой модификации. 11. [М10) Какой путь на решетке (аналогичной представленной иа рнс, П) соответствует перестановке 1 2 5 3 7 4 б б 9 11 10 12? 12. [М20) Докажите, что сумма вертикальных весов пути на решетке равна числу инверсий соответствующей 2-упорядоченной перестановки.
ь 13. [М16) Поясните, как нужно приписать веса на решетке горизонтальным ошрсэкагг вместо вертикальных, чтобы сумма горизонтальных весов пути на решетке равнялась числу инверсий в соответствующей 2-упорядоченной перестановке. 14. [М20) (а) Покажите, что для сумм, определяемых равенством (2), действительно Агюп = 2Аг„. (Ь) Если пцзожить г = г, г = -2, то обобщенное тождество в упр. 1.2,б-26 упрощается и приводится к виду ~2?г+ г) г 1 (1 — ч1 — 4г) Проанализировав сумму 2 „Ат„о", покажите, что Ат =п ° 4" '.
йо(х) = 1, йс(о) = о, йо(х) = ' + '; йт(х) = о, р (о) се Ьо(о) = 1, Ьт(г) = о + 1, Ьт(х) = хо + о' + зо + 1; Ьс(о) = х + 1, Ьо(о) = о + и Найдите ренуррентпые соотношения, определяющие этн функции; и воспользуйтесь полу- ченными рекуррентными соотношениями для доказательства равенства 7по + 4пт + 4тт ( 2тс ) ЗО (Отсюда легко можно найти точную формулу дисперсии числа инверсий в случайной 2-упорядоченной перестановке множества (1, 2,..., 2п) кона асимптотнчески приближается „ ( т )по ) 16.
[М24[ Найдите формулу максимально~о числа инверсий в )ьупорядоченной перестановке множества (1,2,...,п). Каково максимально возможное число перезаписей при выполнении алгоритма П, если значения смещений для сортировки удовлетворяют услоэию делимости (5)? 17. [М21[ Покажите, что если Ьт = 2' и Ь, = 2' прис > о > О, то существует единственная перестановка множества (1, 2,..., п), максимизнруюшая число перемещений записей црн выполнении алгоритма Р.
Найди ге простой способ описания этой перестановки. 18. [НМ24) При больших значениях Ьт сумму (б) можно считать равной Ко /?~оттЬстт ЬтотоЬпт ' '+" + Ьо 4Ь,т В Ьсо + о 15, [ЯМА) Пусть у„(о), у„(х), Ь„(х) и Ь„(х) равны 2 х'" "" '""", где суммаберется по всем путям длиной 2п па решетке от (О,О) до (п, п), где веса определяются, как на рнс. 11, а пути удовлетворяют некоторым ограничениям на нершины, через которые эти пути проходят. Для Ь„(о) нет ограничений, но для д (о) пути не должнм проходить через вершины (т, т), такие, что с > т'; Ь (х) и й„(х) определяются аналогично, но не допускаются также и вершины (т, т) при О < т < п.
Таким образом, Каковы действительные значения Ьс т,..., Ьо, минимизирующие это выражение, если Ь' и 1 фиксированы, а Ьо = 1? ° 10. [Мйб[ Каково среднее значение величиям А в анализе времени работы ттрограммы Р, если значения смещений при сортировке удовлетворяют условию делимости (5)? 20. [МЯУ[ Покажите, что теорема К следует из леммы 1,. 21. [М25] Пусть Ь и lс — взаимно простые целые положительные числа. Будем говорить, что целое число — порохсдаемое, если оно равно хЬ+ рЬ при некоторых неотрицательных целых хо и ро.
Покажите., что п является порождаемым тогда н только тогда, когда ЬЬ - Ь вЂ” Ь вЂ” и — не порождаемое. (Поскольку Π— наименьшее порождаемое целое, наибольшее не порохсдаемое должно, таким образом, быть равно ЬЙ вЂ” Ь вЂ” Й. Отсюда следует, что э любом массиве, который является одновременно и Ь-, и Ь-упорядочентсым, К; < К , если толысо т' — т > (Ь вЂ” 1)(Ь вЂ” 1).) 22. [Мур[ Докажите, что любое целое число > 2'(2' — 1) можно представить в виде ао(2' — 1) + ас (2'~ — 1) + ао(2'~~ — 1) + . где ໠— неотрицательные целые числа; но число 2'(2' — 1) — 1 нельзя представить в таком виде.
Более того, существует ровно 2' '(2' + е — 3) целых положительных чисел, которые нельзя представить в таком виде. Найдите аналогичные формулы для случая, когда в этом представлении выражение 2 — 1 заменено выра»капнем 2 + 1. л л ь 23. [МЗЗ) Докажите, что если Ь,+е и Ь„т» — взаимно простые числа, то количество перезаписей в ходе выполнения алгоритма О прн просмотре со смещением Ь, есть 0(»УЬ,т»Ь,+»/Ь,).
(Указание. См. упр. 21.) 24. [Май) Докажите, что теорема Р— наилучшая нз возможных теорем в том смысле, что показатель 3/2 нельзя уменьшить. ь 25. [МЯЗ) Сколько существует перестановок множества (1, 2,..., Ь»), являющихся одновременно 3- и 2-упорядоченными? Каково максимальное число инверсий в такой перестановке? Чему равно суммарное число инверсий во всех таких перестановках? 26. [МЗЗ) Может ли 3-, 5- и 7-упорядоченный массив из М элементов содержать более Ф инверсий? Оценпте максимальное количество инверсий прн болыпом Ь».
27. [М41) (Бьерн Пунен (В)огн Роопеп).) (а) Докажите, что существует константа с, такая, что если»п из смещений Ь, в алгоритме О имеют величину, меньшую»Л?/2, то время выполнения будет в худшем случае равно П(Ь»» ы» "»ц). (Ъ) Следовательно, время выполнения алгоритма О будет в худшем случае равно й(?Л»(!ой Ь»/!о8!о8»Л»)~) для всех последовательностей смещений. 28. [15) Какая из последовательностей смещений, указанных в табл.
б, наилучшая для программы О с точки зрения суммарного времени выполнения сортировки? 29. [зд) Найдите для Ь» = 1000 н различных значений 1 эмпирические значения Ь» Ь», Ье, которые, быть может, минимизируют среднее число операций перемещения записей В, в алгоритме О. 30. [МЗУ) (В. Пратт (У. Ргасс).) Покажите, что если множество смещений при сортировке методом Шелла есть (2гЗе [ 2вЗе < )7), то число проходов равно примерно .»1(!ой» Ф)(!ойз д?) и на каждый просмотр прях»лднтся не более Ь»/2 операций перестановки записей. В действительности„если К л > К», то на любом проходе К»-зл,К»-ы < К» < К»-л < К»+л, К»+ы; так что можно просто поменять местами Кз л н К» и увеличить 1' на 2Ь, сэкономив два сравнения в алгоритме О. (Указание. См. упр.
25.) ь 31. [85) Напишите ИХХ-программу для алгоритма сортировки, предложенного Праттом (упр. 30). Выразите время ее выполнения через параметры А, В, Я, Т, »Л?, аналогичные соответствующим параметрам в программе О. 32. [1О) Каково будет окончательное содержимое связей Ха В» . Еы, если провести до конца сортировку списка посредством вставок в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
