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