Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 107
Текст из файла (страница 107)
(50) а последнее уравнение при х, близком к О, при помощи уравнения (39) преобразу- ется в 2а( )+2л(2 ) =а( )+О( )+а(*/(1+*)). (53) После подстаиовки в зто уравнение степенных рядов вместо фуикций коэффициенты при 18х в обеих частях должны быть приравнены.
Следовательио, 2а(2х) — 4Лх = а(х) — Лх + а(х/(1+ х)). (54) Уравиение (54), определяющее а(х), — рекурреитиое. Действительно, предположим, что функция 1Ь(2) удовлетворяет уравнению 1Ь(х) = — (2+41(-) + 1/1~ — )), ф(О) = О, Ф'(О) = 1.
(55) Тогда уравнение (54) означает, что а(х) = -Л6(х). 3 2 (56) Более того, из итерационного уравнения (55) следует 1 1 1 1 1 1 1 1 1 '(.) =++++ — )+++ — + — + — )+ ") =-Š— Е— 2 1 1 2 22 „21+Ух ййе 0<1<Ы Отсюда получаем, что обобщение Ф(2) для степенных рядов имеет вид в-1 1Ь(2) = ~~1 (-1) -~1Ьвхе 1Ье ~~1 ' ( ) + .
(58) а>1 2=О см. упр. 27. Эта формула удивительио похожа иа выражение 6.3-(18), полученное в свя:зн с алгоритмами дискретного поиска в дереве, а в упр. 28 приводится доказательство справедливости формулы Ф„= сг(п 2). Теперь нам известно а(х), за исключением случая, когда Л = -р1 постоянно. Уравнение (50) связывает функции д(х) и р(х), исключая козффициеит р1.
Из ответй к упр, 25 видно, что все козффициенты функции р(х) могут быть выражены через р1, рз, ры .. БОлее ТОГО кОнстанты и и гц ИОГут быть вычислеиы при помощи метода, применяемого для решения задачи в упр. 29; при атом между козффициеитами функций у (х) иб (х) сохраияютсясложныесвязи. Тем ив менее, похоже, что едипствениым способом вычисления всех коэффициентов для различных функций. входящих в выражение для С(х), является итеративное решение рекуррентного уравнения (36) численными методами.
После вычисления хорошего приближения к 0(х) можно оценить среднее время выполнения алгоритма Б следующим образом. Если и > е и если выполнить й сдвигов вправо, то величина У = ие будет заменена иа 1" = (и — е)е/2 . Значит, У/У' равно 21/(1-Х), где Х = е/и равно > х с вероятиостью С(х). Отсюда следует, что число битов в ие уменьшается в среднем иа константу г1 Ь = Е18(Ъ'/1") = ~~1 2 "(/2(0) + / С(х)/ь(х)1гх), Ф>1 е где /ь(х) = 15(2ь/(1 — х)) . Получаем ,( /' О( )И* ) /' Я*!"* (59) 2/Ь = О.
70597 12461 01916 3915293141 35852 8817666677+. (60) В результате более глубокого анализа этих функций Бригитта Валле (Впб(ые таНЬе) высказала предположение, что постоянные Л и Ь могут быть связаны примечательной формулой Л 2(п2 (61) Ь тз Значения, вычисленные Брентом, вполне согласуются с этим далеко нетривиальным утверждением. Вызывает большой интерес анализ алгоритма В, успешно выполненный Валле на основе строгих "динамических" методов (см. А!8огййписа 22 (1998), 660-685). Вернемся к предположению в (32), состоящему в том, что и и и нечетные и изменяются в интервалах 2~ < и < 2~+' и 2" < и < 2"+'. Эмпирические испытания алгоритма В, проведенные с несколькими миллионами случайных значений на входе и с различными значениями гп и и, взятыми из интервала 29 < гп, и < 37, показывают, что в действительности усредненное поведение алгоритма определяется соотношениями С ж -'ш + 0.203я+ 1.9 — 0.4(0.6)~ ", гп> и.
(62) 11 и ги+ 0.41п — 0.5 — 0.7(0.6) при довольно небольшом стандартном отклонении от наблюдаемых средних значений. Коэффициенты -' и 1 при пь в выражениях (62) могут быть строго проверены (см. упр. 21). Если же предположить, что ц и и — любые целые числа, независимо и равномерно распределенные в интервалах (63) то можно вычислить средние значения величин С и В по уже имеющимся данным: С 0.70У+ 0(1), 11 ж 1.41Х+ 0(1).
(64) (См. упр. 22.) Это хорошо согласуется с результатами последующих эмпирических экспериментов, выполненных с несколькими миллионами случайных входных данных для Х < 30. Эти эксперименты показали, что в качестве подходящих значений При и = е ожидаемое значение числа 16ие будет приблизительно равно 0.9779 (см, упр. 14), поэтому общее количество циклов "вычитание и сдвиг" алгоритма В будет приблизительно равно исходному значению числа 16 ие, умноженному на 1/Ь, Учитывая свойство симметрии, это количество приблизительно равно исходному значению числа (бп, умноженному на 2/Ь, В результате выполненных в 1977 году вычислений Ричард Брент (Блспагб Вгепс) получил для этой фундаментальной константы значение для заданных распределений входных данных и н в можно взять (65) С = 0.70Ю вЂ” 0.5, ?2 = 1.41?0 — 2.7.
Теоретический анализ непрерьшной модели Брента алгоритма В предсказывает, что при предположениях (63) величины С н ?7 аснмптогическн равны 2Х/Ь и 4?0/Ь, где 2/Ь 0,70597 — константа в (60). Согласование с результатами экспериментов настолько хорошее, что константа 2/Ь Брента<b>Текст обрезан, так как является слишком большим</b>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
