AOP_Tom3 (1021738), страница 175
Текст из файла (страница 175)
Но сумма д(х, у) по всем д парам (х, д), таким, что х шос1 6 = Ь и д спос1 6 = с лля любого данного Ь ф с, и есть общее количегтво инверсий в случайной 2-упорядоченной перестановке 26)/6 элементов. Таким образом, как следует из упр. 14, среднее значение д(х, у) равно д '~/л/128 (2)б/6)~) ~ + О(М/д6) (Ь) См. С. Б. 3апеоп, Р. Е. Кпигб, Еаа)4от Бггасгигпд алс1 Л!8з. 10 (1997), 125-142. Если 6 и д велики, имеем д)(6,д) = ь/л66/1289+ О(д ')~6'/~) ч- О(д6 Од). 43. Если К < К) после шага РЗ, присвоить (К),...,К ь,К)) +- (К,К),,К, «); в противном случае выполнять шаги Р4 и Р5 до тех пор, пока К > К,.
Здесь 1 = 1, еш)и 1 = 6 ч 1, а 1 с — 1+ 1 — 6 [1=6], если у увеличивается на 1. [См. Н. Ч~. ТЫспЫеЬу, Яа/д)гаге Ргасйсе дс Ехрег. 19 (1989), 303-307.] Другая идея повышения скорости выполнения программы состоит в том, чтобы при 6 > 1 выполнять сортировку только частично, не пытаясь продвинуть К, влево далее позиции д — 6 [см. дд2 РоЬошеж)сг, 1яб Ргос.
6ессегд 11 (1980), 5. 8], но, кажется, этот подход требует больше смещений. 44. (а) Да. Это очевидно в случае, когда )г' оказывается на один шэг "выше"' л; в упр. 5 1.1-29 показано, чта при таких условиях существует путь от л к любой перестановке над ней. Этот путь образован операциями транспоннрования соседних элемедпюв. (Ь) Да. Аналогично, если л расположена "выше" л, то л расположена "ниже" л'Я. (с) Нег; 21 3 не будет ни "выше", ни "ниже" 31 2, но 2 1 3 < 3 12. [Частичное упорядочение л < л' было впервые проанализировано Ч.
Эресманом в контексте алгебраической топологии (С. ЕЬгеэшапп, ЛааэЬ оГМаСЬ. (2) 35 (1934), 390 — 443, 320). Многие математики называют его теперь порядком Брюа перестансвок.] РАЗДЕЛ 5.2.2 1. Нет, в ней на 2т+ 1 инверсий меньше, где т > 0 — числа элементов ад. таких, что б < Ь < у и а; > ад > а,. (Следовательно. любая обменная сортировка, в конце концов, приводит к упорядоченной перестановке.) 2. (а) б.
(Ь) [А. Сау!еу, РЬ)1од. Мэд. 34 (1849), 527-529.] Рассмотрим циклическое представление перестановки л. Если поменять местами элементы ддидгд и того дбсе цикла, то число циклов дееличигпся на 1; если поменять местами элементы рагимх циклов, то число циклов уменьшится на 1. (Это, по существу, содержание упр. 2.2.4-3.) Полностью рассортированная перестановка характеризуется тем, что она имеет и циклов.
Следовательно, хсй(л) равно п минус число циклов перестановки л. [Алгоритм 5.2.35 выполняет ровно хсЬ(л) операций обмена записей; см. упр. 5.2.3 .4.) 3. Да; относительное расположение равных элементов никогда не меняется. 4. Это вероятность того, что в таблице инверсий будет Ь) > шах(Ьд,...,Ь ). Вероятность равна с Дб" -') ~!=Д )б О) ')= бсг )<д<д 5. Можно считать, что г > О. Пусть 6[ = (Ьс — г + 1) [Ь, > г] — таблица инверсий после г — 1 проходов. Если Ьс > О, то элементу б предшествует 6'; больших элементов, наибачьший из которых всплывает, по крайней мере, до позиции 6) +б (так как имеется б элементов < б). Кроме тога.
если элемент ! — крайний справа среди всех элементов, которые предстоит обменять, то Ь' > О и после г-го прохода ЯООИО = Ь,' + ! — 1. 8. Решение !. Элемент, наиболее удаленный вправо от своего конечного положения, перемещается н(годин шаг влево прн каждом просмотре, кроме последнего. Решение 2 (более высокого уровня). Из упр.
5.1.1-8, ответ (1), а', — ! = Ь, — с, прн 1 < ! < и, где с! ср... с„— двойственная таблица инверсий. Если Ь = шах(6(,,6„), то с! = О. . (с( ~((!+с(! — с(,((-с(п(-г(Г!'"=дг-' ((-+о(!. 8. При ! < 6+ 2 имеется !+ й — с+ 1 способов выбора 6,; при й+ 2 < ! < и — !+ 2 имеется ! — 1 /ч1 способов; при ! > и — ! + 2 имеется и — ! + 1 способов.
10. (а) Если !' = 2!с — 1, то из (й — 1, а, — й) в (й, а, — !с). Если ! = 2й, то нз (а! — й, й — 1) в (а, — й, й). (Ь) Шаг арь ! выше диагонали с=» !с < арь ! — й 4=» аы ! > 2й с=» аы-! > аы 4=» аы < 2й — 1 с=» арь — й < й — 1 4=» шаг арь выше диагонали, Если поменять этн элементы местами, то поменяются местами горизонтальный и вертикальный шаги.
(с) Шаг ар!+с будет, по крайней мере, на т единиц ниже диагонали с== й+тл — 1 > ам+с — (й+ гн) + т с=» ар»эх < 2й+ т с=» аы > 26+ та 4=» арр — й > й+ го <==» шаг арю (Если арьес < 2й + т и арр < 2й + т, то имеется не менее (й + т) + й элементов, мепыпнх, чем 2й+ т, а это невозможно. Если арьес > 2й+ т и аы > 2!с + т, то один из знаков ">" должен быть знаком "> "; но невозможно поместить все элементы < 2й+ т в менее чем (й+ т) + й позиций. Следовательно, арььр ! < арь тогда и только тогда, когда арь ьр ! < 26+ т, т. е.
когда 2й+ т < ар!. Довольно неожиданный результат!) 11 16 10 13 5 14 б 9 2 15 8 11 3 12 4 7 1 (б1 обмен). Ответ получается в результате анализа решеточной диаграммы. Ситуация усложняется, егли 7(г велико; в общем случае множество (Кр, Кс,... ) должно быть таким: (1, 2,..., М вЂ” 1, М, М + 2, М + 4,..., 2 (д(/2) — М); и его перестановка должна максимизировать число обменов для ()с'/2) элементов. Здесь М = (2"/3), где й макснмизнрует й(Ж/2! — -'((Зй — 2)2ь-' + ( — 1)"). Суммарное максимальное число операций обмена записей равно произведению 1 — 2 18 18 !с/18 (р(+ 0(1/ (об 7!() н числа сравнений (К.
Бес(8ев'рсй, ЯСОМР 7 (1978), 239 — 272). 12. В следующей программе, написанной В. Панин (%. Равпу), команда АИО не исполь- зуется — лля этого шаг М4 выполняется прн ! = г+ 2йр+ з. й > О н О < з < р. Здесь ТТ щ 2, р = гП, г = г12, с ра г13, р + (( — (р( эз г14 и р — 1 — э щ г15: полагается, что Ж > 2. — ! — 1 О! ЯТАНТ ЕИТ1 ТТ 1 М1. Ини нализ ия . р с- 2' 08 2Н ЕИТ2 ТТ Т М2. Иня налива ня г ((. ОЭ ЯТ2 О(1:2) Т д+- 2' 04 ЕИТ2 0 Т г !†О. 05 ЕИТ4 0,1 Т г14 +- (4.
05 ЗН ЕИТЗ 0,2 кЗ,р ! 07 1ИС4 -И,З А г14+- !+Π— )У. ОЭ ЯН ЕИТЬ -1,1 В + Е з +- О. 00 4Н 1.91 1ИРОТ+1,3 С М4. С ааненяе обмен В (В !О СИРА 1ИРОТ+И+1,4 С !! Л.Е с+4 С Переход, если К,.»! < К,+се!. !Я ЬОХ ХИРОТ+8+1,4 В !Э ЯТХ 1ИРОТ+1,3 В гс,+! »Ф Л +с+!. !4 ЯТА 1ИРОТ+И+1,4 В 15 152 7Р С Переход, если э = р — 1. !О ЮЕСЯ 1 С вЂ” .0 э с- э + 1, !7 1ИСЗ 1 С вЂ” В р с- ! + 1. !В 1ИС4 1 С вЂ” В д <- 51/2. г14 +- 52. Перейти к шагу МЗ, если б( ~ О Мб.
о~ ббл 19 14М 4В С вЂ” Р Повторить цикл, если 5+51 ( /Лб, 20 ЗНР 52 Е Иначе перейти к М5. 21 7Н ТМСЗ 1,1 Р 5 о- 5+р+ 1. 22 ТМС4 1,1 Р ЯЭ 14М 4В Р Повторить цикл, если 5 + с( ( 55'. 24 5Н ЕМТ2 0,1 ~М5. 25 0 ЕМТ4 б А г14 л- 9. Яб ЕМТА 0,4 А 27 БВВ 1 А ЯЭ 5ТА 0(152) А ЯЭ ВЕС4 О, 1 А ЭО 14Р ЗВ А Э! БН ЕМТА 0,1 Т ЭЯ 5ВВ 1 Т ЭЭ БТА о+1(1;2) Т ЭА ЕМТ1 м т р — (р/2). ЭБ 11МЗ 2В Т Перейти к шагу М2, если р ф О. А Время выполнения зависит от шести параметров, из которых лишь один зависит от исход- ных данных (остальные пять являются функциями только от 555): Т = 1, числа "внешних циклов"; А = 1(С+ 1)/2, числа просмотров, или бвнутренних циклов", В = числу обменов (перемениолбу); С = числу сравнений; Р = числу блоков последовательных сравнений; Е = числу неполных блоков.
Если 5'б' = 2', то можно показать, что Р = (1 — 2)Л5+ 1+ 2 и Е = О. Для данных из табл. 1 Т = 4, А = 10, В = 3+0+1+4+0+0+8+0+4+5 = 25, С = 63, Р = 38, Е = О, так что общее время выполнения равно 11А+БВ+1ОС+2Е+12Т+1 = 939и. Панин показал, что в общем случае Р = еб(Ж+ 1) — 2(2" — 1), Е = (" '") + (ел + еа+ . + е„ 5) — (ел — 1)(г — 1), если !55 = 2" + . + 2'".
13. Нет, так же, как и алгоритмы СА и К. 14. (а) Если р = 1, то при последнем слиянии выполняем (2' ' — О) + (2' ' — 1) + (2'"'— 2)+(2' ' — 4)+...+(2' ' — 2' ) = (! — 1)2' '+1 сРавнений; (Ь) хб = х, 5+-'(1 — 1)+2 ' = =хо+2 л 5(-'6+2 л ') = -'(5)+1 — 2 '. Следовательно, с(2') =2' '(1~ — 1+4) — 1. 15. (а) Рассмотрите число сравнений, таких, что 5+ 55 = !б'; затем примените индукцию по г. (Ъ) Если 6(п) = с(а+ 1), то имеем Ь(2п) = а(1)+ +а(2п) = а(0) +а(1)+а(1)+ ..+ а(п — 1) + а(п) + х(1) + х(2) + . + х(2п) = 26(п) + р(2п) — а(п); аналогично Ь(2п+ 1) = 26(п) + р(2п + 1). (с) См.
упр. 1.2.4-42. (51) Весьма трудоемкие вычисления выражения (х(бл!) + 2х((Лл/2) ) + .. ) — а(!б ) с использованием таких формул, как 2 (и — А)=2"т' — и — 2, ~ 2 ( ) =2"+' — ( ) — 1, л=о л=о приводят к результату Р) =Ю(-( )+ге, 1) — г' (е, — 1) — 1 'л 2 'л 2 ) 1 геб — еЗЛ +7 2" (еб+ +е 5 — 1(ел — 1)+ — ( !)) 5 2 2 5=1 16. Рассмотрим (о„") путей иа решетке из (О,О) в (п,п), как на рис. 11 и 18, и присвоим серии от (55!) до (5 + 1,!) вес /(5 — !), если 5 > 1, и /(Я вЂ” 5 — 1) + 1, если ! ( 1; здесь /(Ь) — число изменений разрядов Ьб ~ Ь,лб в двоичном представлении А = ( .. 656|Ьо)о, Если !55 = 2п, то общее число обменов в окончательном слиянии равно 2 о(о<5<„(2/(!) + 1)(~7 ))(~"„~',~~, '). Р.
Седгевик показал, что в общем случае / эта сумма упрощается и пРиводитсЯ к видУ -"(~") + 2 2 >, ( ~'„) 2 е« /(У); затем он использовал метод гамма- функции и получил асимптотическое выражение ) ~-п18п+ ~18 + — + — +б(я)) и+0(ь/и!обп)), ()~ 2п1 /1 Г Г(1/4)э 1 7+ 2 и) ~4 1 2я 4 41л2 где Б(п) — периодическая функция 18 и с огршшчеиной амплитудой .0005. Следовательно, в среднем около 1/4 сравнений приведет к обмену при и -> со. ($1СОМР 7 (1978), 239-272; см. также Иаю1ей 061ухйо, $1АМ У. Р1зсгесе МагЛ. 3 (1990), 238-239.) 17. Значение Кл+~ проверяется при сортировке подмассива, для которого г = Х и К~-- наибольший ключ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
