2. Анализ алгоритма Евклида

Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи.

Суть последовательности Фибоначчи в том, что начиная с 1,1 следующее число получается сложением двух предыдущих.

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ….

Приступим к анализу алгоритма Евклида. Нас будет интересовать наихудший случай -- когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n О--N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F--_{n +2} , b = F--_{n +1} , где F--_k -- k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N О--N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает

й--log _Ф ( Ц--5  N ) щ--- 2,

где й--a--щ--- верхнее целое a--, F--= (1 + Ц--5)/2 -- больший корень характеристического уравнения последовательности Фибоначчи.

log _Ф ( Ц--5 N ) »--4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за й--4,785 · 6 + 1,672 щ--- 3 = 31 - 3 = 28 шагов.