§ 10. Качество оценок

85

Для дальнейшего будет полезным следующее свойство чисел Фи­боначчи:

F_n-₁F_n+1 = (-1)ⁿ, n = 1,2, ... (10.6)

(доказывается индукцией по п). Рассмотрим вложенные отрезки Φ₁ э зΦрΦ₃э... числовой прямой:

f2„ f2„+1

п = 1,2,

Φn

^2п f2 +1 2n-1 , F 2n

1

Соотношение (10.6) позволяет установить, что ни один из этих

Очевидно, что

F 2n-1 F 2„

отрезков не пуст и что длина отрезка Φ_n равна

Φ₁ = [1, 2] (рис. 15). Далее можно доказать, что если рациональное

р₂

F₄

Р₆

ф

F₇

F₅

T₄

Р₃ P₂

Рис. 15. Расположение чисел

F_n

и интервалов Φ_n, n=1, 2,

число — принадлежит Φ_п, п > 2, то деление а₀ на а₁ дает ненулевой

a₁

a₁

остаток а₂, и — принадлежит Φ_п-1. В самом деле, мы имеем

Р2п-1 «1 Р2п

Следовательно, частное от деления а₀ на а₁ с остатком равно 1, т. е. а₂ = а₀ - а₁. Далее,

а0 ^- а1 а0

⁼⁼ — - 1

а₁ а₁ ,

поэтому

Р2п-1 «1 Р2п

Но

Р2п Р2п-1

1 Р2п-Р2п-1 Р2п-2

Р2п-1 Р2п-1 ,

86 Глава 3. Оценивание числа шагов (итераций) алгоритма

и, аналогично, ^2п+1 - 1 = ²"~^г; мы имеем, следовательно, „²"~² ^ — ^

Р2п F 2n Р2п-1 «1

^и

-^^^-1 (₁₀₇)

F 2n-i^a 2^F 2n-2- ^U

Получаем

_Mte-te=Φ~

£i_G Jk. ^ _c ^1 ^n-T

a 2 F 2n_!F 2n_2 F 2n_3 F 2n-2

Отрезки Φ₂,Φ₃, ... не содержат целых чисел, поэтому из доказанного можно заключить, что если г е Φ_п n Q, п > 2, то C'_E{r) ^ п. Пусть теперь фиксировано а_г&П⁺. Рассмотрим множество

М = \r: r=—, a_n = ai,ai +1, ... к а₁ ^и 1 1

Точки, соответствующие элементам множества М, расположены на правой полуоси, начиная с 1, с шагом —; хотя бы одна из этих точек

непременно принадлежит отрезку Φ„, коль скоро — меньше длины

отрезка Φ_п, т. е. — ^ ■= =—, или, что то же самое, а_г ^ F_2n_iF_2n. Пусть

JV — самое большое значение п, для которого выполняется это нера­венство (такое JV существует, так как единственной точкой, принад­лежащей бесконечному числу отрезков рассматриваемого семейства, является ф £Q). Тогда F_2NF_2N+1>a₁. Из формулы Бине следует, что

f₂nF_2N+i = |ф^4М(1 - (-ФГ^4Ы)(.Ф - С-ФГ^4АГ_1),

откуда

W2N+1 < СФ^4Ы,

где с — некоторая положительная константа. Таким образом, сф^4Ы > > а_г и

1

JV > i log^ а_г - \о%_ф

с.

1

Имеем С'_Е(г) ^ N - 1 > ^ log₀ a_x - log₀ с - 1 по крайней мере для од­ного рационального числа геМ, откуда следует соотношение (10.4). Переходя к размеру входа т = Х{а_г), мы можем воспользовать­ся теоремой 4.2 из § 4 и получить для сложности Т^{т) по числу

§ 10. Качество оценок

87

делений соотношение T*(m) = в(m). (В силу теоремы 4.2 T*(m) = = n(log2^m-¹) = n(m) и T_E*(m) = O(log2^m) = O(m).)

Число шагов расширенного алгоритма Евклида (см. пример 9.1) совпадает с числом шагов обычного алгоритма Евклида. Мы получа­ем следующее:

Если рассматривать a_г как размер входа (a₀, a_г) расширенного алгоритма Евклида, то для мультипликативной сложности T_ЕЕ(.a_г) этого алгоритма выполнено T^fa^ =Q(loga₁). При рассмотрении m = А(a_х) в качестве размера входа a₀, a_г расширенного алгоритма Евклида имеем для мультипликативной сложности оценку T*_Е{m) = = в(m). Все это сохраняет силу и для сложности T*{m) «обычного» алгоритма Евклида.

Запись алгоритма Евклида в форме (9.1) далека от записи в виде «приличной» компьютерной программы не только в смысле исполь­зованной символики, но, главное, в смысле предписываемого расто­чительного расхода памяти (использован массив, и при буквальном следовании алгоритму (9.1) мы бы имели S_Е(,a_г) = QfJogaJ). С точ­ки зрения программирования более приемлемой будет, например, запись

a:=a₀; b:=a₁; while b>0 do

d:=rem{a,b); a:=b; b:=d od

(rem—знак операции нахождения остатка). После выполнения алго­ритма имеем a = нод(a₀, a_г). Использовано только три дополнитель­ных переменных (a,b и d), и мы получаем S_E(a₁) = 3.

Оценку (10.4) можно усилить, показав, что найдется константа у' такая, что

T_E(a₁)>|log_(#,a₁+r^/ (10.8)

(см. задачу 54). Часто в литературе оценки снизу для сложности в худ­шем случае алгоритма Евклида по числу делений выводят из оценки, полученной в 1970 г. Г. Хейлбронном для сложности в среднем:

T_E(a₁) = ^j^lna₁+O(l). (10.9)

Последняя оценка обосновывается весьма непросто. Из (10.9) выво­дится, что

T_E(a₁)>i^lna₁+_r^//

88 Глава 3. Оценивание числа шагов (итераций) алгоритма

для некоторой константы f. Однако при больших а_г оценка (10.8) для Т_Е{а_г) является более строгой (ИЩ1 \_пф = 0,40554... < |) и вдо­бавок выводится элементарно ^г.

Может быть доказано (см. задачу 52), что Т_Е{а_г) <\о%_ф а_г + с, где с —некоторая константа (заметим, что log₀ 2 = 1,44... < 2) ².

Рассуждения, сходные с приведенными при доказательстве нера­венства (10.4), показывают, что для каждого а₀ можно подобрать а_ъ а₀ ^ а_ъ так, что будет выполняться

C_E(a₀,a₁)>|log₍^a₀ + /3, (10.10)

где /3 — некоторая константа. В данном случае можно рассмотреть вложенные отрезки Ф_х э Ф₂ ^{D ф}з ^D •••:

Ф„=[^²-,%-¹], п = 1,2,

(при п> 1 отрезок Ф„ не содержит чисел вида —, meN⁺); если a_n не делится нацело на а_х и — g Ф_п, то — е Ф_п__х и т.д. Мы воспользуемся этим в § 21.

Пример 10.2. Сортировка массива длины п бинарными вставка­ми выполняется за п — 1 шаг, причем на Z-м шаге число сравнений не превосходит [log₂(Z + 1)] и, следовательно, не превосходит [log₂ п\ на любом из шагов, —это приводит к оценке (9.14). Возникает вопрос, не сможем ли мы получить существенно лучшей оценки сверху, рас-

п-1

смотрев сумму X! riog₂CZ + 1)1, которая совпадает со значением Т_в{п),

т. е. сложности по числу сравнений (такое число сравнений достига­ется, например, в случае, когда изначально массив имеет обратную упорядоченность: х_г > х₂ > ... > х_п). Замена переменной суммирова­ния дает

п

r_B(n)=^riog₂Z<l. (10.11)

fc=i

¹ Приведенный выше и дополненный в указании к задаче 54 элементарный вывод оценки (10.8) принадлежит М. Оналбекову; в [19, разд. 4.5.3, упр. 38] со ссылкой на статью Я.Микусинского (1954 г.) приведена оценка, фактически совпадающая с (10.8), но ее вывод опирается на теорию цепных дробей и не столь элементарен и нагляден.

² Предположение о том, что T_E(aj) ~logj, а_ь насколько известно автору, не доказано и не опровергнуто (2008 г.).