Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2)

Эта теорема явилась первым практическим применением последовательности чисел Фибоначчи. С тех пор числа Фибоначчн нашли широкое применение при выполнении и исследовании алгоритмов. Следующий результат получил Т. Ф. де Ланьи (Т. Г. де 1 айну) [Мбш. Асад. Ясз Рапз 11 (1733), 363-364). Он составил таблицы нескольких первых К-полиномов и обнаружил, что числа Фибоначчи дают для цепных дробей заданной длины наименьшие числитель и знаменатель. Однако он совсем не имел в виду вычисление наибольшего общего делителя. Первым иа связь между числами Фибоначчи и алгоритмом Евклида указал Э. Леже (Е. Ьфбег) (Соггеэропдалсе МасЬ. ес РЬуэ)опе 9 (1837), 483-485), Вскоре после этого П. Ж.

Е. Финк (Р. 3. Е. Гшс1с) (ТгшМ Йешекга)ге д'Аг11Ь- шеВщце (81гаэЬоцг8, 1841), 44] другим методом доказал, что если и > в > О, то 8сд(и е) вычисляется не более чем за (2!8 с+1) шагов, а Г Ламе (О. Еаше) (Сошрсеэ Иепдиэ Асад. Яа. Рапэ 19 (1844), 867-870) распространил полученный результат на 5(1об,е(с+ 1)), Полное изложение этих пеРвых Работ по анализУ алгоРитмов поавилось в интересном обзоре Дж.

О. Шэллита (3. О. БЬа1!В) Наела МагЬешаг1са 21 (1994), 401-419. Однако более точная оценка наихудшего случая является прямым следствием теоремы Г. Следствие 1. Если 0 < е < )у, то число шагов деления, необходимых алгоритму 4.5.2А для выполнения операций с числами и и в, не превышает~1оба (3 — ф))У~~. Доказагасльсглво. После выполнения шага А1 имеем с > и шод и. Поэтому согласно теореме Г максимальное число шагов и имеет место в том случае, когда в = Г + ~ и ц шод и = Г„.

Так как Г„+, < Ь7, то ф"+'/м5 < Х (см. 1,2.8-(15)). Следовательно, ф" «Аф)"К=(3 ф)ж. Величина 1обэ (3- ф) Ф приближенно равна 2.078 1п )у+ .6723 ж 4. 78о 1ойш Ю + .6723. По поводу обобщений теоремы Г обратитесь к упр. 31, 36 и 38. Приближенная модель. Теперь, когда известно максимально возможное количество шагов деления, попытаемся найти их среднее число. Пусть Т(т, и) — число шагов деления в случае, когда алгоритм Евклида имеет на входе и = гп н о = о. Тогда Т(т,0) = О", Т(ш, и) = 1+ Т(п,гл пюд и) при и > 1. (18) Пусть ҄— среднее число шагов деления, когда и = и, а и выбирается случайным образом. Поскольку после выполнения первого шага деления на ход выполнения алгоритма влияет только значение ц пюд е, можно записать Т„= — ~ Т(Ь, и).

(19) о<яки Например, Т(0, 5) ж 1, Т(1, 5) = 2, Т(2, 5) = 3, Т(3,5) = 4, Т(4, 5) = 3, так что Ть -- -'(1+ 2+ 3+4+3) = 2$. Задача состоит в оценке Т„при больших значениях и. Попробуем сначала применить приближение, предложенное Р. У. Флойдом (В. ЪЪ'. Г1оуд). Можно предположить, что для 0 < Ь < и значение и, по существу, "случайно" по ькдулю Ь, так что можно записать 1 Т„~м 1+ — (То+ Т~ +. + Т„~). Тогда Т„ш 5„, где последовательность (Я„) есть решение рекуррентного соот- ношения оэ=О, Я =1+-(Бе+81+ +5 1), п>1. и Это рекуррентное соотношение легко решить, есэи учесть, что 1 Ба+1 = 1+ (со+ с1 + ' '+ сп-~ + Бп) и+1 = 1+ — (п(5„— 1) + 5„) = Я„+ —. 1 1 и+1 и+1 Следовательно, Я„равно 1+ 1+" + 1 = ̈́— гармоническому числу, Теперь приближение Т„ш Я„дает Т„1п и + 0(1).

Сравнение этого приближения с таблицами истинных значений Т„показывает, однако, что 1п и — это слишком много. (Т„возрастает не так быстро.) Предположение, что число и случайно по паулю Й, является по этой причине слишком пессимистическим. И в самом деле, более внимательный анализ показывает, что среднее значение числа и шод Й меньше среднего значения числа 1Й при 1 < Й < и: — (ишобЙ) = — ~~~ (и — 4Й) 11п/(4+1)) < Й < (п/4)1 1 1 15ьба 1йддбп 1,. йьм+1) (мд+~н+~)) 1 Е (~~и+1) 1<а<я яэ1 1 — — ~ п+ О(1ойи) 12/ (21) (см, упр. 4.5.2-10(с)) Это равно примерно .1775и, а не .25и.

Поэтому значение п щи Й меньше значений, предсказываемых моделью Флойда, а а чгоритм Евклида выполняется быстрее, чем предсказывает приближенная модель. (22) Й'„(я) = Рг(Х„<л) при 0< к <1 Непрерывная модель. Прв о = )О поведение алгоритма Евклида, по существу, определяется поведением правильной цепной дроби для Х = О/74, 1/уг' ... ...; (Р7 — 1)/Ф, При очень больших Ю естественно рассматривать разложение числа Х в правильную цепную дробь фактически как случайного вещественного числа, равномерно распределенного в интервале [0..1). Рассмотрим функцию рас- пределения равпомерио распределенного числа Х = Хс. По определению правильных цепных дробей получаем Ре(х) = х и Р ~1(х) = Ч~~ ' Рг(Ь < 1/Х < Ь+ х) = ~Ч ' Г (17(Ь+ х) < Х„< 17Ь) = ~ч ' (Р„(175) — Р.(17(Ь +х))).

(23) Если распределения Ре(х),Р1(х),...„определяемые зтими формулами, сходятся к иредельному распределению Р (х) = Р(х), то получаем Р( ) = Е(Р(1Ю-РМЬ+*))) (24) (Аиелогичное соотношение, 4.5.2-(36), было получено при рассмотрении бинарных алгоритмов определения наибольшего общего делителя.) При любом основании Ь > 1 одна из функций, удовлетворяющих уравнению (24), имеет вид Р(х) !обь(1+ х) (см. упр. 19). Из дополнительиого усяовия Р(1) = 1 следует, что Ь = 2. Таким образом, вполне обосновано предположение, что Р(х) = )В(1+ х) и что последовательность Р„(х) сходится к зтому пределу. Можно было бы предположить, например, что Р(В) = )В(уг) ~и 0.58496. Посмотрим, иасколько близко Р„(-') к атому значению при малых и.

Имеем Щ) = 0.50000 и Р,(х)=Я-- — ) =Н. 1 1 ьйг Рг ф = Н17г = 2 — 2 !п 2 ю 0.61371; Рг(т) = Нг7г — Нгуг + Нгг4 — Нг~г + Нее — Нгуг + (см. табл. 3 приложения А). Обобщение иа степенной ряд Н, = ~(2)х — ДЗ)хг + ~(4)хг — ДВ)хг + "° позволяет определить численное значение Рг(г) = 0.57655932769991408418 82618 72122 27055 92452 — . (26) Получаем значение, близкое к О.о8496. Но совсем не очевидно, как получить хорошую оценку Р„(г) при и = 3, т. е. при значеиии, меньшем, чем те зкачения, которые считаются действительно большими.

Впервые распределения Р„(х) были исследованы К. Ф. Гауссом (С. г. Сааза), 'который начал решать зту проблему 5 февраля 1799 года. В его записях за 1800 год перечислены различные рекуррентпые соотношения и приведена краткая таблица значеиий, включающая (неточные) приближения для Щ) ~ 0.5748. После завершеиия зтих вычислений Гаусс записал: "Таш сошр)!сасж атас)ппц ос по1!а зрее зпрегеше тк!еагцг", т. е. "Они получаются такими сложными, что, кажется, нет никакой надежды". Двенадцать лет спустя Гаусс написал письмо Лапласу„в котором сформулировал эту проблему как таковую, для которой он не смог найти удовлетворяквцего его решения.

Он писал: еВ результате простых рассуждений я обнаружил, что Г„(х) = )ой(1+ х)/1о82 для бесконечного и. Но все дальнейшие попытки, предпринятые мною для оценки Р„(я)-1о8(1+я)/1о82 для очень бвтьших, но конечных значений и, были безуспешны". Гаусс так никогда и не опубликовал свои "очень простые рассуждения", поэтому не совсем ясно, нашел ли он строгое доказательство. (См. Оапээ'э )4'егке, то!.

10', 552-556.] Прошло более ста лет, прежде чем такое доказательство бььпо, наконец, опубликовано Р. О. Кузьминым в Айй сЫ Сопйтеато 1пгегпаязогта)е с(е! Ма!с!пабе! 6 (Во)ойпа, 1928), 83-89, который показал, что Р„(я) = !8(1+ х) + О(е " ") для некоторой положительной константы А. Остаточный член О(е "") был получен вскоре после этого Полем Леви (Рап! !.4ту) (ВиГь 5ос. Май. !!е Ргапсе 67 (1929), 178-194)*. Но проблема, сформулированная Гауссом, которая заключается в поиске асимптотического поведения функции Г„(я) - !8(1+ х), фактически не была решена до 1974 года, пока Эдуард Вирсинг (Е!(пагг! %цпв!п8) не опубликовал ее блестящий анализ (Асса Аьййп!ег!са 24 (1974), 507-528). Здесь мы исследуем самые простые аспекты приближения Вирсинга, поскольку его метод основан на использовании линейных операторов, Если Π†произвольн функция я, определенная на интервале 0 < х ( 1, то определим функцию 5С в виде Таким образом, 5 есть оператор, переводящий функцию из одного состояния в другое.

В частности, нз соотношения (23) получаем 5'„+з(х) = 5Ге(я); тогда (28) (В данн!!м случае 5'„означает функцию распределения, а не числа Фибоначчи.) Заметим, что 5 — "линейный оператор", т, е. 5(сО) = с(5О) для всех постоянных с, и 5(а! + аз) — 5ьт! + 5ьтз ° Теперь, если для О существуют ограниченные первые производные, выражение (27) можно почленно продифференцировать и показать, что (29) так что функция 5О также имеет ограниченную первую производную.

(Почленное дифференцирование сходящегося ряда оправдано в том случае, когда равномерно сходится ряд, составленный из производных; см., например, К. Кнорр, ТЬеогу апд Аррйсабоп о! 1пбшсе 5егзш (61аэйоас В1асЫе, 1951), 147.) э Изложение интересного доказательства Леви приведено в первом издании этой книги. Тогда Гэ(х) = х, /е(х) = 1+х и Д(х) есть постоянная функция, равная 1.

Покажем, что оператор 6™ переводит постоянную функцию в функцию, принимающую очень малые значения, поэтому при 0 < х < 1 значение )В'„'(х)~ должно быть очень малым. Покажем также, что функция В„(х) сама по себе мала. Так как выполняется соотношение В„(0) = В„(1) = О, согласно знакомой интерполяционной формуле (см, упр.

4.6.4 — 15 для случая, когда хе = О, х« — — х, хэ = 1) для произвольной функции („(х), где 0 < ~„(х) < 1 при 0 < х < 1, функция В„(х) имеет вид Вя(х) = — — В'„'(6,(х)). (Зб) Таким обрезом, все сводится к попытке доказать, что П" порождает функции с малыми значениями, где (/ — линейный оператор, определяемый уравнением (31).

Заметим, что (/ — полохсншв«ьнмй оператор в том смысле, что если для всех х у(х) > О, то и У~р(х) > О. Отсюда следует, что оператор У сохраняет порядок: если ~р~(х) < уз(х) для всех х„ то Грд(х) < (/срз(х) для всех х. Один из способов использования этого свойства заключается в поиске функции х, для которой можно вычислить точное значение У~р и использовать константу, кратную этому значению функции, для определения верхней границы интересующей нас функции. Сначала рассмотрим такую функщ«ю д, чтобы можно было легко вычислить значение Тд. Если рассмотреть функции, определенные для всех х > О, а не только на отрезке [О .. Ц, то можно исключить в (27) суммирование, заметив, что для непрерывной функции С выполняется соотношение ЯС(х+1) — ЯС(х) =С~ — ) — йш С( — ) =С~ — ) -С(0) (37) Из того, что Т((1+х)6") = (1+ х)(ЯС)', следует (см. упр.

20) Тд(х) Тд(1+ х) ~ ) д ~ 1 ) (ЗЕ) Если положить, что Тд(х) = 1/(1+ х), то находим, что соответствующее значение функции д(х) равна 1+ х — 1/(1+ х). Положим:р(х) = д'(х) = 1+ 1/(1+ х)з, так что (7р(х) = -(Тд)'(х) = 1/(1+ х)~. Функция х и является искомой функцией. Прн таком выборе функции 1« получаем 2 <,р(х)/Гр(х) = (1+ х)э + 1 < 5 при О < х < 1. Следовательно, уд<(/д< Ь. Так как функции У и э~ положительны, можно снова применить оператор (/ к згому неравенству и получить з««з < 1Уу < Уз~о < зУ'с < 1у. После (и — 1)-го воздействия оператора У на неравенство получаем для конкретного значения ~д следующее выражение: 5 "Ф<(/ау<2 "Ф.