Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 35
Текст из файла (страница 35)
П1енхаге (А. 8с!юпЬабе) очень близко подошел к доказательству этого факта (см. упр. 28). еАсимптотнческне значения, Из теоремы С следует, что получение точных значений 1(п) при болыпих и является, по всей видимости, очень трудной задачей. Однако можно определить приближенное поведение функции в предельном случае, когда п -э оо. Теорема Р (А. Вгацег, Ви!!. Ащег. Май. Яос.
45 (1939), 736-739). (23) 1цп Г(п)/Л(п) = !!зп 1(п)/Л(и) = 1, Доказательство. Алдитпвная цепочка (4) для 2ь-арного метода является звездной, если удалить из нее все вторые вхождения каждого элемента, встречающегося в цепочке дважды. Если а,— первый элемент среди 24~, 44~, ... второй строки, который отсутствует в первой строке, имеем а, < 2(т — 1); следовательно, а; = (т — 1) + аэ для некоторого а в первой строке.
Суммируя общую длину цепочки, получаем Л(п) < !(и) < ! (п) < (1+1/1)18п+ 2ь (24) для всех Й > 1. Утверждение теоремы можно получить, если, например, выбрать й = 1118Л(п)). 1 Если положить к = ЛЛ(и) — 2ЛЛЛ(п) в (24) для больших и, где ЛЛ(п) означает Л(Л(п)), получим более строгую асимптотическую границу 1(п) < Г(п) < Л(п) + Л(п)/ЛЛ(п) + О(Л(п)ЛЛЛ(п)/ЛЛ(п) ).
(25) Второй член Л(п)/ЛЛ(п) является, по существу, лучшим из того, что можно получить из (24). Можно провести более глубокий анализ нижних границ, чтобы показать, что этот член Л(п)/ЛЛ(п) является неотьемлемой частью (25). Чтобы понять, почему это так, рассмотрим следующую теорему. Теорема Б (Рац! Егббэ, Асса Апйшег!са 6 (1960), 77-81). Пусть с — положительное действительное число. Китчество алдптлвных цепочек (11), такгхх, что (26) Л(п) = т, г < т+ (1 — е)т/Л(т), меньше, чем а"', для некоторого о < 2 для всех достаточно больших гп. (Другими словами, число влдитивных цепочек, столь коротких, что удовлетворяется соотношение (26), существенно меньше количества значений и, таких, что Л(п) = т, при больших гл.) Ч=(х»-А)+" +(1»-у») можно получить 2»»М < и < 2г-ч(1+ б)эа — 2ци)ь*-»х-в)в < 2»,Ю+*-»»-в»» Воэвраишясь к доказательству теоремы Е, выберем б = 2ем — 1 и разделим г шагов каждой алдитивной цепочки на три класса: 1 мини-шагов, и удвоений, с прочих шагов, 8+ и+ е = г.
(29) При другом способе подсчета шагов получим в малых шагов, где в+ел = г. Иэ наших предположений, теоремы А и леммы Р получим соотношении в < (1 — в)их/Л(ьч), 1+с < 3,271в, 1< в/(1 — в/2) (30) Для данных в, 1, и и и, удовлетворяющих этим условиям, существует (,.",,) = ~,"Л",") (31) способов назначения шагов определенным классам. Прн заданном распределении шагов рассмотрим, каким образом могут быть выбраны не мини-шаги. Если шаг х' является одним из "других" шагов в (29), а» > (1+ б)а»», так что ໠—— а + а», где ба» х < а» < а < а»», Кроме того, а.
< а»/(1+ б)» х < 2а»»/(1+ б)» х, поэтому б < 2/(1+б)» х. Это дает не более,9 выборов х, где»у — константа, зависшцаи только от б. Имеется также не более д выборов й, твк что количество способов назначения 7 и к для каи»дога не мини-шаха не превышает ))эь И наконец, как только х' и й выбраны для каждого из не мини-шагов, имеется менее © (33) Доииаихельсихео. Чтобы оценить количество возможных адлитнвных цепочек, сначала необходимо улучшить теорему А, и это позволит иам более успешно работать с неудвоениями. Лемма Р. Пусть б <»/2 — 1 — фиксированное положительное дейстинтельное число.
Наэоиел» шаг( адаптивной цепочки мини-шагом, если это не удвоение и если а» < а (1 + б)» х для некоторого х, где О < у < 1, Если аддитивиая цепочка содержит 8 малых шагов и х мши» шахов, то С < в/(1 — д), где (1+ б)э = 2в.
(27) Доказан»ельси»ео. Для каждого мини-шага 1», 1 < /х < 1, имеем а;„< ах„(1+ б)" х' для некоторых уь < х». Пусть 1»,..., 7» — интервалы (х» .. »»],..., Ц» .. »»], где запись (у ..1] означает множество всех целых чисел й, таких, что у < Й < х. Можно найти (см. упр. 17) такие неперекрывающиеся интервалы 7»,...,,1» -- (,у»' ..»х],..., (Я, »»], 1» О" 01» = Ух».х" ».» Ю», (28) а < ау (1+ б)ц» хИ для 1 < /х < Ь. Теперь для всех шагов», находящихся вне интервалов 1»,..., 1», имеем а» < 2а; х, следовательно, если положить способов выбора.( и й для мини-шагов: выбираем 1 различных пар (зл, ал) ° ° (А йл) индексов в диапазоне О < кл < ул < г меньшим числом способов, которые заданы в (ЗЗ). Затем для каждого мини-шага 4 используем пару индексов (ул, йл), такую, что а) ул<л; Ь) аэ„+ ел, принимает наименьшее возможное значение среди еще неиспользованных для меньших мини-шагов л пар; с) а; = ау„+ ал„удовлетворяет определению мини-шага.
Если таких пар (лл, йл) не существует, адаптивная цепочка не будет получена; с другой стороны, .любая алдитивная цепочка с мини-шагами на назначенных местах должна быть выбрана одним из этих способов, так что (33) представляет собой верхнюю границу имеющихся возможностей. Таким образом, общее количество возможных аддитивных цепочек, удовлетворяющих (26), ограничено сверху величиной (31), умноженной на (32) и на (33), которая просуммирована по всем подходящим э, 1, и и е. Доказательство теоремы Е теперь может быть завершено стандартными оценками этих функций (см.
упр. 18). $ Следствие. Величина 1(п) асимлтогическн равна Л(п) + Л(п)/ЛЛ(п) для почти всех и. Более строго говоря, существует функция /(п), такая, что /(п) -+ О лри Рг( ~1(п) — Л(п) — Л(п)/ЛЛ(п) ~ > /(и) Л(п)/ЛЛ(п) ) = О. (34) (См. определение вероятности "Рг" в разделе 3.5.) Доказательство. Верхняя граница (25) показывает, что (34) выполняется без знаков абсолютного значения. Нижняя граница вытекает из теоремы Е, если положить следующее: /(п) уменьшается до нуля достаточно медленно, чтобы прн /(и) < е значение Ж было настолько велико, чтобы не более еДг значений и < Х имели 1(п) < Л(п) + (1 — с)Л(п)/ЛЛ(п). $ «Звездные цепочки, Оптимисты сочтут оправданным предположение о том, .что 1(п) = ('(п); трудно поверить, что по данной алдитивной цепочке минимальной длины 1(п) нельзя найти цепочку той же длины, удовлетворяющую условию звездности (по-видимому, слабому).
Однако в 1958 году Вальтер Хансен (%а!сег Напэеп) доказал замечательную тлюрему о том, что для определенных больших значений и значение((п) строго меньше, чем 1'(и), а также ряд связанных с ней теорем, которые мы сейчас и рассмотрим. Теоремы Хансена начинаются с исследования детальной структуры звездных цепочек. Пусть и = 2" + 2" + "+2"„где ее > ел » ° ел > О, и пусть 1 = ао < ел « .. а, = и — звездная цепочка для и.
Если ватой цепочке имеется И удвоений„определим вспомогательную последовательность (35) 0=4> <Ил «(э « " л(„=И, где И~ —.количество удвоений среди шагов 1, 2, ..., л1 Также определим последовательность "мультимножеств" ос, ол, ..., Я„, которая будет отслеживать наличие степеней 2 в цепочке. (Мультпмножество (тийиел) представляет собой математический объект„подобный множеству, но он может содержать одинаковые элементы. Объект может быть элементом мультимножества несколько раз, причем кратность его появления в множестве имеет важное значение. Более подробно с мультимножествами вы ознакомитесь в упр.
19.) Мультимножества 5» определены следующими правилами: а) 5о =(0); Ь) если аьь» = 2аь то 5» ь» = 5» + 1 = (х + 1 ~ х Е 5»); с) если а,+» = сч + аы й <», то 5» ь» = 5»»в 5ы (Символ 'е» означает, что мультимножества объединяются со сложением кратностей.) Из этого определения следует, что (36) где члены суммы необязательно различны, в частности 2ео 1 2»» 1 . + 2е» ~~~~ ~2х хез (37) Число элементов в последней сумме не превышает 2Х, где Х = г — »( — количество неудвоений. Поскольку и имеет два различных бинарных представления в (37), мультимножество 5„можно разбить на мультимножества Мо, М», ..., М», такие, что 2*'= ~~» 2*, 0<у<а (38) е > х > е. — т для всех х Е ЛХ .
(39) Наше исследование структуры звездных цепочек завершается построением мультимножеств М», в которых записана история МХ. Мультимножество 5, разбито на Х + 1 мультимножеств следующим образом: а) М„з = ЛХх, Ь) если аьь» = 2оь то М»1 — — М»»».»»» — 1 = (х — 1! х е М~»».ц~); с) если а»+» =а»+ам к <», то, поскольку 5»+» = 5» е»5ы полагаем, что Мп = Мц+щ минус 5ь, т.
е, мы удаляем элементы 5ь из М»»+»» . Если некоторый элемент 5» появляется в двух или более различных мультимножествах М»»».»бч удаляем его из множества с наибольшим возможным значением Х. Это правило однозначно определяет М» для каждого Х, когда» фиксировано. Из данного определения следует, что (40) для всех л Е М»Х. ез+»»»»(>л>еХ+»»»»( пъу Данную операцию можно выполнить, разместив элементы 5„в порядке неубывания х» < лз < " и взяв М» = (л»,хы...,хь), где 2*' +" + 2*' = 2". Это должно быть возможно, поскольку е» вЂ” наименьшее из всех е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
