AOP_Tom2 (1021737), страница 143
Текст из файла (страница 143)
Она состоит из одного из шести типов, перечисленных в доказательстве теоремы В, малого шага и последовательности немалых шагов. Будем говорить, что и "специально", если и = 2~ + 2в + 2С + 2~ для одного из четырех случаев, перечисленных в теореме. Можно получить влдитивные цепочки требуемого вида для каждого специального и, как показано в упр. 13, позтому остается доказать, что не существует цепочек с точно двумя малыми шагами, содержащих любые элементы с и(а,) > 4, за исключением специального аь Назовем цепочкой-контрпримером адаптивную цепочку с двумя малыми шагами, такую, что и(а,) > 4, но а, не является специальным.
Если цепочка-контрпример существуез; то рассмотрим цепочку 1 = ао < а~ < < а„= и наименьшей возможной длины. Тогда шаг т не является малым шагом, поскольку ни одни из типов цепочек из доказательства теоремы В не может предшествовать малому шагу с и(п) > 4, за исключением специального и. Кроме того, шаг т не является удвоением, так как более коротким контрпримером была бы цепочка ао,..., а„ь Наконец, шаг т является звездным, так как иначе цепочка ао, ..., а„о, а„представляла бы собой более короткую цепочку-контрпример.
Таким образом, а„ = а„ , + а„ ю й > 2, и Л(а,) = Л(а„ ~) + 1. (21) Обозначим число переносов, встречающихся при сложении а„~ н а„ь в двоичной системе счисления по алгоритму. 4.3.1А, как с. Используя фундаментальное соотношение и(а,) = и(а„~) + и(а„ь) — с, (22) можно доказать, что шаг т — 1 не является малым (см. упр. 14). Пусть т = Л(а, ~). Поскольку ни т, ни т — 1 не является малым шагом, с > 2; равенство с = 2 может быть справедливо только тогда, когда а„~ > 2тв + 2 Теперь предположим, что т — 1 — не звездный шаг. Тогда т — 2 — малый шаг и ао, ..., а, з, а, ~ представляет собой цепочку с только одним малым шагом. Следовательно, и(а, ~) < 2 и и(ат о) < 4.
Соотношение (22) может выполняться, только если и(ат) = 4, и(а, ~) = 2, й = 2, с = 2, и(а, о) = 4. Из с = 2 можно заключить, что ат ~ —— 2"'+2 ', следовательно, ао, ам ..., а, з — — 2 '+2"' о является аДдитивной цепочкой с только одним малым шагом и зта цепочка должна быть первого типа, так что а„относится к случаю 3. 'Хаким образом, т — 1 является звездным шагом.
Теперь предположим., что а, ~ — — 2'а, ь для некоторого б Если и(а„у) < 3, то в соответствии с (22) с = 2, к = 2 и а, должно относиться к случаю 3. С другой стороны, если и(а„~) = 4, то а„, будет специальным, и при рассмотрении каждого случая легко видеть, что а„также относится к одному из четырех случаев. (Случай 4 возникает, например, когда а„, = 90, ат ь = 45 или когда а, у = 120, ат ь = 15.) Поэтому можно заключить, что а„з ф 2'а, ь для любого б Мы доказалн, что а„з — — а„о + а„о для некоторого д > 2. Если й = 2, то 4 > 2 и ао, аз, ..., а„о, 2ат з, 2ат в + а„, = а„представляет контрпример последовательности, у которой й > 2. Поэтому можно считать, что й > 2.
Теперь предположим, что Л(ат в) = тп — 1. Случай, когда Л(ат ь) < пт — 1, может быть исключен в результате подобного рассмотрения, как показано в упр. 14. Если й = 4, то и т — 2, и т — 3 являются малыми шагами; следовательно, а„з = 2 и (22) невозможно. Поэтому !г = 3; шаг г — 2 является малым, о(а, э) = 2, с = 2, а„~ > 2'о + 2"' ' и и(а,,) = 4.
Должно существовать как минимум два переноса при сложении чисел а, э и а, ~ — а,. ю Значит, и(а, э) = 4 и ак в (будучи специальным и > -'а„~) имеет вид 2ж '+2'" э+2аь'+2" для некоторого И. Теперь а„~ равнолибо2'"+2' '+2"+'+2э,либо2м+2'" г+2эеэ+2э+' и вобоихслучаях а„э должна быть равно 2"' ' + 2'" э, так что а„относится к случаю 3. 1 Э. Е Тюрбер (Рас!бс Х Магй. 49 (1973), 229 — 242! расширил теорему С для показа того, что !(и) > Л(п) + 4 при и(п) > 8. Представляется обоснованным предположение, что !(и) > Л(п) + 18 и(п) в общем случае, поскольку А.
Шенхаге (А. Яспбпйабе) очень близко подошел к доказательству этого факта (см. упр. 28). *Асимптотические значения. Из теоремы С следует, что получение точных значений !(и) при больших и является, по всей видимости, очень трудной задачей. Однако можно определить приближенное поведение функции в предельном случае, когда п, — у оо. Теорема 1У (А. Вгапег, Ви!!.
Атег. Магй. Яос. 45 (1939), 736 — 739). (23) 1пп !'(и)/Л(п) = 1пп !(п)/Л(п) = 1. Доказательство. Алдвтивная цепочка (4) для 2ь-арного метода является звездной, если удалить из нее все вторые вхождения каждого элемента, встречающегося в цепочке дважды. Если а,— первый элемент среди 2Но, 4Но, ... второй строки, который отсутствует в первой строке, имеем а, < 2(т — 1); следовательно, а, = (т — 1) + а! для некоторого аэ в первой строке. Суммируя общую длину цепочки, получаем Л(п.) < !(и) < ! (и) < (1+ 1/й) !8п+ 2ь (24) для всех !с > 1.
Утверждение теоремы можно получить, если, например, выбрать !с = ('- !8Л(а)). Если положить !с = ЛЛ(п) — 2ЛЛЛ(п) в (24) для больших и, где ЛЛ(п) означает Л(Л(п)), получим более строгую асимптотическую границу !(и) < 1*(п) < Л(п) + Л(п)/ЛЛ(п) + 0(Л(п)ЛЛЛ(п)/ЛЛ(п) ). (25) Второй член Л(п)/ЛЛ(а) является, по существу. лучшим из того, что можно получить из (24). Можно провести более глубокий ввализ нижних границ, чтобы показать, что этот член Л(п)/ЛЛ(п) является неотьемлемой частью (25). Чтобы понять, почему это так, рассмотрим следующую теорему.
Теорема Е (Рап! Егбов, Асса Аг!г!т~ег!са 6 (1960), 77 — 81). Пусть г- — положительное действительное чггсло. Количество алдитлвных цепочек (11), таких, что (26) Л(п) = гп, г < т+ (1 — е)т/Л(т), меньпш, чем а'", для некоторого а < 2 дл» всех достаточно больших т. (Другими словами, число аддитивных цепочек, столь коротких, что удовлетворяется соотношение (26), су.щественно меньше количества значений и, таких, что Л(п) = т, при больших т.) Доказательство.
Чтобы оценить количество возможных алдитивных цепочек, сна- чала необходимо улучшить теорему А, н это позволит нам более успешно работать с неулвоениями. Лемма Р. Пусть д < чг2 — 1 — фиксированное положительное действлтельное число. Назовем шаг1 адаптивной цепочки мини-шагом, если это не удвоение и если а, < а (1+ б)' 1 для некоторого 7', где 0 < 7' < 1.
Если вддптнвная цепочка содержит в малых шагов н $ мини-шагов, то где (1+ д)~ = 2~. г < в/(1-6), (27) Доказательство, Для каждого мини-шага»», 1 < и < г, имеем и;„< а,„(1+ 5)'" '" для некоторых 7» < г». Пусть Хы..., 1, — интервалы (у1 ..11],, (7~ .. й], где запись (у ..1] означает множество всех целых чисел Й, таких, что 7' < Й < 1. Можно найти (см. упр. 17) такие неперекрывающиеся интервалы /м...,,7» = (71 ..»1],,(Я,. Р»], что Х с~ 1~7~ = у О ~~,7», (28) вг < ау (1 -~- 6)тр1 »И для 1 < й < )ь Теперь для всех шагов», находящихся вне интервалов,7ы ...,,7», имеем а; < 2а,. П следовательно, если положить Ч = Я - А ) + " + (1» - Й) можно получить 2»~ч> < п < 2 -ч(1+ д)еч — 2Мч~ч -П-в)э < 2»~ ~ч -О-аи $ Возвращаясь к доказательству теоремы Е, выберем 6 = 2ох — 1 и разделим г шагов каждой адлитивиой цепочки на три класса: 1 мини-шагав, и удвоений, е прочих шагов, 1+ и+ ц = г.
(29) При другом способе подсчета шагов получим в малых шагов, где в+т = г. Из наших предположений, теоремы А и леммы Р получим соотношения з < (1 — с)т/Л(п1), »+ е < 3.271г, 1 < в/(1 — с/2). (30) Для данных в, 1, и и е, удовлетворяющих этим условиям, существует (,;,,) =(„',)(",') (31) И наконец, как тачько 7' и 1с выбраны для каждого из не мини-шагов, имеется менее й (ЗЗ) способов назначения шагов определенным классам. При заданном распределении шагов рассмотрим, каким образом могут быть выбраны не мини-шаги.
Если шаг 1 является одним из "других" шагов в (29), а; > (1+ б)а; ы так что а; = а + а», где Бв, 1 < о» < ву < вч., Кроме того, а < а;/(1+5)' 1 < 2а;,/(1ч-Б)' 1, поэтому б < 2/(1+6)' ~. Это дает не бачее 3 выборов 7', где 3 — константа, зависящая только от б. Имеется также ие более б выборов к, так что количество способов назначения 7 и Й для каждого не мини-шага не превышает 32ю (32) способов выбора у' и /с для мини-шагов: выбираем 1 различных пар (уы ЛЭ),..., (уа Й~) индексов в диапазоне О < игл < ул < г меньшим числом способов, которые заданы в (ЗЗ). Затем для каждого мини-шага 1 используем пару индексов (ул, йл), такую, что а) ул<$; Ь) агл + ал„принимает наименьшее возможное значение среди еще неиспользованных для меньших мини-шагав 1 пар; с) а, = ау„+ ал„удовлетворяет определению мини-шага.
Если таких пар (ул, 1сл) не существует, аддитивная цепочка не будет получена; с другой стороны, любая аддитивная цепочка с мини-шагами на назначенных местах должна быть выбрана одним из этих способов, так что (33) представляет собой верхнюю границу имеющихся возможностей. Таким образом., общее количество ваэлшжных алдитивных цепочек, удовлетворяющих (26), ограничено сверху величиной (31), умноженной на (32) и на (33), которая просуммирована по всем подходящим в, Г, и и н. Доказательство теоремы Е те.- перь может быть завершена стандартными оценками этих функций (см. упр. 18). 1 Следствие.
Величина !(и) аснмптотнческя равна Л(п) + Л(п)(ЛЛ(п) для почтп всех п. Более строю говоря, существует функция Дп), такая, что ((и) -у О пря п -э аа я Рг( /1(п) — Л(и) — Л(п)/ЛЛ(п)~ > Д(п)Л(п)/ЛЛ(п) ) = О. (34) (См. определение вероятности "Рг" в разделе 3.5.) Доказашельсшво. Верхняя граница (25) показывает, что (34) выполняется без знаков абсолютного значения. Нижняя граница вытекает из теоремы Е, если положить следующее: Дп) уменьшается до нуля достаточно медленно, чтобы при э(п) < е значение Ж было настолько велико, чтобы не более еХ значений п < Х имели 1(и) < Л(п) + (1 — е)Л(и)/ЛЛ(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
