AOP_Tom3 (1021738), страница 180
Текст из файла (страница 180)
— наилучшая из возможных на фазе построения пирамиды. Интересно, кроме того, отметить, что существует единственная пирамида из ключей (1, 2,, Х), такая, что в течение всей фазы выбора в алгоритме Н значение К тождественно равняется 1. (При Х = 7, например, такой пирамидой будет 7 5 6 2 4 3 1; нетрудно осуществить переход от Х к 1э'+ 1.) На этой пирамиде и достигается максимальное значение В на фазе выбора пирамидальной сортировки (так же, как и максимальное значение ~Х/2) параметра В). Значит, верхняя грюнина значения параметра В, т. е.
наилучшее значение из возможных для всей сортировки, равно Х вЂ” и(Х) + %118 1э') — 20е к~+' + 2. 24. ~~ (18Ь) = (57+ 1 — 2")и + 2„о<э<„5~2 = (йг+ 1)п — (2п — З)2"+~ — 6. где и = (18%) (см. упр. 4.5 2 — 22). Следовательно, дисперсия для последнего протаскивания есть Вя = ((%+1)п — (2п — 3)2" ' — 6)/Ю вЂ” ((Я+1)п+2 — 2" ') /Х = О(1). Стандартное отклонение величины Вк равно (2„(д ~ э Е Мя)) = О(з/М). 26, Протаскивание "равномерно', и каждое сравнение К,:Кгг~ с вероятностью -' дает 2 результат <.
Средний вклад в значение параметра С в этом случае равен в точности половине суммы средних вкладов в значения параметров А и В, а именно — ((2п — 3)2" '+ -')/(2ь ы — 1). 26. (а) ( — '„"„+ г + 1 о + г + 1 г + 1-, + 2-' + -' + 1-' + 1-' + 2-' + 1-' + 2+ 2 + 3 + О+ 1 + 1 + 2 + 1 + 2 + 2 + 3 + 1 + 2 + 2)/26 = 1189/780 1 524 (Ь) (2 „' ! иЯ вЂ” А< + ! (!У/2) — -'и+ 2„„"Т!' ш!п(оь с, сш — оь ! — Ц/(и! — 1))/!У, где и(<с) — количество единиц в двоичном представлении числа 15 а а! = (1Ьь Ьо)г Если Ас = 2" + 2"' + . + 2", гДе е! > ег » ес > О, можно показать, что ~,, о сг(!с) = -'((с!+ 2)2" + (ег+ 4)2" +.
+ (ес+ 2!)2" ) +с — А<. (Асимптотические свойства этой суммы можно проанализировать при помощи преобразования Ь!евнина; см. Р!а)а!ег, СгаЬпег, К!шсЬепЬо(ег, Ргос!шбег, ТссЬу, ТЬеогебса! Сагир. Ясй 123 (1994), 291 — 314.) 27. Дж. У. Ренч (мл.) (3. %. %тепсЬ, Зг.) пришел к выводу, что в общем случае ряд Ламберта 2 „>, а х"/(1 — х") можно представить в виде 2 .>с(~ щи аз)х' = 2 >с(аос+ с то>с(аос+ а чс,)х ) х [На случай, когда а„= 1 и о„= и, первым обратил внимание И. Г. Ламберт (1. Н. ЬагпЬегс) в работе Аа!аде хат Атей!гас!оп!с 2 (Н!Ва, 1771), 1875; Клаузен вывел свою формулу для о = 1 в рабате Сгейе 3 (1828), 95, а Х. Ф.
Шерк (Н. Р, ЯсЬег1с) представил доказательство в Сге!!е 9 (1832), 162 — 163. Если а„= и и х = -', получим соотношение ( ( — ) (2 ° с)) = 2.74403 38887 59488 36048 02148 91492 27216 43114 + . Эта константа появляется в приближенных формулах (20), где В,'ч (сΠ— 2)Ас и Сь. (2<~ 4 г) ') Кстати, если положить д = х и г = хд в первом тождестве из упр. 5.1.1 — 16, а затем вычислить о при д = 1, получим интересное тождества: д ог п>! ! >1 28. Потомками /с-га узда являются узлы 3/с — 1, З)с и 35+ 1; родителем является ((/с+ 1)/3). Время выпшшения 811-программы, аналогичной программе Н, асимптотически приближашся к 21!79!ой уй 13 7Аг!8 Ас машинным циклам.
Используя идею из упр. 18, можно сократить его до 18 гА< !ойг 1!с 11.8А' !8 Ас, хата за счет операций деления на 3 добавится большое слагаемое О(!У). Более подробную информацию а г-парных деревьях можно найти в рабате 8. ОЬоша, /.ессоге !с<о!ео га Сотр. Ягб 88 (1980), 439-.451. 30. ПРедположим, что и = 2' — 1+ г, где ! = (!Вп) и 1 < г < 2'. Тогда Ьгос — (т=О), и получим ! — г 5<„оО < ) (2" — 1)5„<о 1> + 2' 'Ь„< !ос!+ гйо<~ О при и > 2, г=о рассматривая числа элементов на уровне /, которые претендуют стать окончательным "пристанищем" для Ь„о! после того, как ан будет "протянут" на место К!. Таким образом, если д„= И„~/2, получим 2! — 1 г д«„, 7 д„< Л+д„<,,!+ — д„<,! < (!8(пт1)) шахдо 2! 2' ! >о ! =-о из чего по индукции следует до < Бо = Пь г <8 Е Среднее суммарное число продвижений ва время фазы выбора равно Влн = Л;;~ ~ гпЛн >е где Ля = з~,„>вЛн есть суммарное число возможных пирамид (теорема Н).
Известно, что В",, < Х[1КХ). С другой стороны, имеем В~. > т — Лн' з,,(т — Л)Ляь > т— Лч'Хя 2 ~,(гп — Л)2ь > гп — 2 '~Л„~Ья для всех т. Выбор т = 18(Ля/Ьк) + 0(1) дает теперь В",, > 18(Лк/Ья) + 0(1). Число сраннений, необходимых для формирования пирамиды, не превьпнает 2Х, как следует из упр. 23, (Ь), значит, Ля > Л'!/2~~. Очевидно, что Ьл < (18%), и получим 13(Лл/ЬЯ) >%18% Л'1818Ж+ О(Х) [). А)8оп!Лшэ 13 (1993), 76 — 100) 31. (Решение предложено Ю. Эдигхоффер (3.
Еб!БЛо((ег), 1981.) Пусть А — массив, содержащий 2п элементов, причем А[2(!/2)) < А[2() и А[2((/2) — ![ > А[2! — Ц при 1 < ! < п. Кроме того, потребуем, чтобы А[2! — 1) > А[2!) при 1 < ( < и. (В соответствии со структурой пирамид последнее условие выполняется для всех ! тогда н только тогда, когда ано выполняется при и/2 < ! < п.) Эти "пирамиды-близнецы" содержат 2п элементов; если общее чиста элементов нечетно, то один элемент проста хранится отдельна. Для работы с пирамидами-близнецами можно воспользоваться соответствующими модификациями алгоритмов этого раздела; интересно разработать их во нсех деталях.
К этой идее независимо пришли и проанализировали ее авторы работы 3. еан Ьеенвеп, (). 'гесаб, Сашр. Х 36 (1993), 209-216, в которой такая структура названа интервальной пирамидой. 32. В любой пирамиде из Х различных элементов тп = [Х/2"! наибольших элементов образуют поддерево. Не менее [т/2) нз них должны не быть листьями в этом поддереве, поскольку в двоичном дереве с й листьями имеется, па меньшей мере, Л вЂ” 1 элементов, не являющихся листьями. Таким образом, не менее [т/2) из наибольших т элементов окажутся на первых (Х/2) позициях в пирамиде. Эти элементы должны быть продвинуты на позиции в корне прежде, чем они достигнут своего окончательного положения, Следовательно, даля, вносимая в общее число В путем этого перемещения, составляет не менее [ ! [18Л) = —,'т 18т+ 0(т), как следует из упр.
1 2 4 42. Тогда В,„ь(Ж) > 1%18 ь7+ О(Л!) + Выв([Х/2)) и тРебУемый РезУльтат полУчаетсЯ нндУкцией по ЛЛ [1. %е8епег, ТЛеагейса1 Сошр. Зс! 118 (1993), 81-98, теорема 5.1. Р. Шаффер, Р. Седгевнк и независимо от них Воллабан~ (ВойоЬаэ), Феннер (Реппег) н Фризе (Ег(ехе) построили перестановки, которые требуют не менее —.,' Ж 18 )з+ 0()у !о8 1аБ ЛЗ) продвижений; см. Х А!Боп(бшэ 15 (1993), 76 — 100; 20 (1996), 205 — 217. Такие перестановки давольно редки, как следует из упр 30 ) ЗЗ. Пусть Р и Ц указывают на данные приоритетные очереди; как и в основном тексте раздела, в следующем ниже алгоритме полагается, что 01БТ(Л) = О, хотя Л и не нвляется узлам. М1.[Начальная установка ) Установить К е- Л.
М2. [Слияние списков.] Если Ц = Л, усзаиовить П +- П1БТ(Р) и перейти к МЗ. Если Р = Л, то установить Р з- Ц, 0 з- 91БТ(Р) и перейти к МЗ. Иначе, если КЕТ(Р) > КЕТ(Ц), установить Т +- НТСНТ(Р), КТСЫТ(Р) е- Н, К +- Р, Р е- Т и повторить шаг М2. Если КЕТ(Р) < КЕТ(Ц), установить Т +- К1СНТ(Ц), 31СНТ(Ц) +- й, Н +- Ц, Ц е- Т и повторить шаг М2. (Этот шаг, по сути, сливает два "правостаронних списка" данных деревьев, при этом в поля К1СНТ временно помещаются указатели вверх.) МЗ. [Выполненоу[ Если Н = Л, завершить выполнение алгоритма; Р указывает на ответ М4. [Зафиксировать паля 9131.[ Установить Ц е- 31СНТЦК) .
Если 9131(ЬЕРТ(й) ) < 9, та установить 9 е- 9131(ЬЕРТ(й) ) +1, КТСНТ(К) з — ЬЕРТ(Н), ЬЕРТ(К) е — Р; иначе-- устанаяить 0 +- О+ 1, 810НТ(В) о- Р. Наконец, установить 01ЯТ(В) о- О, Р +- В, В+- Ц и вернуться к шагу МЗ. $ 34. Начав с рекурревтного соотношения для составляющих обобщенной производящей функции Х(х) = 2"„>о!„зп = ) „,>, Х (в), >'" где Х (х) = хо + порождает левосторонние деревья с кратчайшим путем длиной т от корня до Л, Райнер Кемр (Кашег Кегнр) доказал, что Х(х) = х+-'Х(г) +-'2„>о Хоп(х) и что а — 0.25036 иЬ 2.7494879 (см, !пй Ргос.
Х.емего 25 (1987), 227-232; Вапйош СгарЬо '8? (1990), 103-130). Луис Трабб Пардо ((.шэ ТгаЬЬ Рагс)о) в 1978 году обратил внимание на то, что производящая функция С(х) = хХ(х) удоилетворяет очень изящному отношению С(в) = и Ь С(хС(г)). 35. Пусть пале 01ЯТ исключенного узла раино 4о, а поле 01ЯТ слитых поддеревьев равно А. Если 4о = А, то подниматьгя вверх вообще не нужно. Если 8о > А, то затем А = йо — 1, и если подняться на и уровней, та поные поля 01ЯТ предков узла р будут равняться соответственно А -Ь 1, А + 2, ..., А + и. Если о(о < А, восходящий путь даожен вести только влево. 36. Вместо обобщенной приоритетной очереди проще всего воспользоваться двусвязным списком: при "использовании" узлов помещайте их в один конец списка, а исключайте— с другого конца.
(См. анализ "самоарганизующихся" массивов в разделе 6.1.) 37. В бесконечной пирамиде самый большой )г-й элемент с равной вероятностью может оказаться н в правой, я в левой падпирамидах сапега большего предка. Таким образам, можно использовать теорию цифровых деревьев поиска и получить е()о) = Сь — Сь ~ и обозначениях выражения 6.3-(13). Как следует из упр, 6.3 — 28, получим е(Ь) = 18 Л + 7/(1п 2)+ о — а+Хо(й)+О(Л' ') 181-.274, где а определено в (19), або(Л) — . периодическая функция )8)о.
(Р. Ъ'. ГоЫе(е, ВХТ 33 (1993), 411-412 ) 38 ЛХо = 8; ЛА = (1); ЛХк = ()Х) Ы ЛХ>ь, М ЛХн о> прн Ж > 1, где )с = (18(2)У/3)). РАЗДЕЛ 5.2.4 1. Начните с В = = (ь = 1, 5 = 1. Теперь повторяйте следующие операции: найти шш(хь,,...,хы„) = х„„и установить г, = х„., Х +- Х+ 1, м +- и -Ь 1. (В этом случае будет удобна положить,.что х,(,„,+,) = оа.) Если Л не слишком велика, то желательно хранить ключи хон,..., хь,„в виде древовидной структуры, которая позволяет осуществлять многократный выбор, как обсуждалось в разделе 5.2.3; тогда потребуется всего (18 Л) сравнений, чтобы найти кажлый новый минимум, кроме первого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
