Глава 3

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

§ 9. Функции, убывающие по ходу выполнения алгоритма

Часто выполнение алгоритма является последовательностью однотип­ных шагов (итераций). Если все шаги равнозатратны по времени, то общее их число с точностью до постоянного множителя эквивалентно временным затратам рассматриваемого алгоритма для данного вхо­да, и важной задачей является определение или хотя бы оценивание числа этих шагов.

Пример 9.1. Пусть а₀, а₁ —натуральные числа, а₀^а₁. Поиск наи­большего общего делителя (нод) чисел а₀, а₁ по алгоритму Евклида требует выполнения серии однотипных шагов, каждый из которых— деление с остатком:

a₀ = q₁a₁ +а₂, а₁ = q₂a₂ +а₃,

(9.1) а_п-3 = Чп-2а_п-2 + а_п-1

a„-2 = q n-1 a„-1 + a n ,

^ап-1 = Чп^ап.

В этом случае а_п = нод(а₀, а₁), так как

нод(а₀, а₁) = нод(а₁, а₂) =... = нод(а_п, 0) = а_п.

Последовательность получаемых остатков убывает (остаток меньше делителя), при этом все остатки — неотрицательные целые. Не су­ществует убывающей бесконечной последовательности, элементами которой являются неотрицательные целые числа, поэтому выполне­ние алгоритма Евклида (будем обозначать его буквой E) завершается для любых натуральных а₀, а₁, и число делений с остатком не пре-

§ 9. Функции, убывающие по ходу выполнения алгоритма 75

восходит а_г. Обозначив через С_Е{а₀,а_г) исследуемое число делений с остатком, получаем

С_Е(.а₀,а₁)^а₁ (9.2)

(для упрощения записи мы пишем С_Е(,а₀,а_г) вместо С^{а₀, а_г)). Это говорит о том, что если а_г рассматривается как размер входа или ес­ли а₀, а_г рассматриваются как два параметра размера входа, то слож­ность алгоритма Евклида по числу делений не превосходит а_г. Как мы увидим, эта оценка является весьма грубой, но, привлекая сход­ные рассуждения, можно получать и более тонкие оценки.

Формализуем те соображения, которые привели нас к этой первой оценке. Каждый шаг алгоритма имеет дело с парой неотрицатель­ных целых {а_{__ъ a_t) и при условии a_t ф 0 перерабатывает эту пару в {a_ha_i+1), где a_i+1 равно остатку от деления а₍__г на a_t. На множе­стве пар неотрицательных целых чисел к, I мы определяем функцию L(fc,Z), принимающую неотрицательные целые значения. Эта функ­ция такова, что когда при выполнении алгоритма Евклида мы пере­ходим от пары {а_{__ъ a_t) к паре (а_ь a_i+1), значения функции убыва­ют: L{a_i_₁,a_i)>L{a_i,a_i+1). Так как функция целочисленна, то ее зна­чение убывает с каждым шагом по крайней мере на единицу. От­сюда следует, что общее число шагов не превзойдет значения функ­ции L на исходной паре чисел. Мы рассмотрели функцию L{k,l) = l, и это привело нас к выводу, что число шагов не превзойдет значения Ца₀,а₁)=а₁.

Для обоснования того, что число делений в алгоритме Евклида растет медленнее, чем а_ъ было бы достаточно найти соответствую­щую функцию I(fc,Z), значения которой при больших к,1 оказывают­ся существенно меньшими, чем Z. Эта функция по-прежнему должна быть определена для любых неотрицательных целых k,l, М Z, прини­мать неотрицательные целые значения и убывать при замене пары М парой I, г, где г — остаток от деления к на Z. Хотя бы одна па­ра целых неотрицательных k,l, к^1, должна обращать L(M) в нуль, иначе вместо L{k,l) можно взять функцию L'(M) = ДМ) - 1 и т.д.

Предложение 9.1. Пусть к,1&П⁺, к>1, и пусть г —остаток от деления к на I. Тогда

(i) A(fc) > А(г), где, как обычно, А(-) — битовая длина данного числа;

(ii) функция

L(M) = A(fc) + A(Z)-2 (9.3)

такова, что L(k, l) > L(l, r).

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

Доказательство. (i) Имеем k = ql + r, q^l, откуда k ^ l + r > 2r. Следовательно, A(k)>A(r).

(ii) Из A(k) > А(r) следует A(k) + A(l) - 2 > A(l) + А(r) - 2. П

Очевидно, что функция (9.3) неотрицательна. Таким образом, справедлива оценка

C_Е(a₀,a₁)^А(a₀)+А(a₁)-2. (9.4)

Но если a₀ очень велико в сравнении с a_г, то А(a₀) + А(a_х) - 2 > a_г. Тем не менее, теперь для C_Е{a₀,a_г) уже легко выводится хорошая оценка. Пусть число делений с остатком больше 1. Имеем

C_Е(a₀, a_г) = C_Е{a_ъ a₂) + 1 s= Х{a_г) + А(a₂) - 1 s= 2А(a_х) - 1.

Оценка

C_Е(a₀,a₁)^2А(a₁)-1, (9.5)

очевидно, верна и в случае единственного деления: C_Е(a₀, a_г) = 1 при том, что \{a_г) ^ 1.

Если взять a_г за размер входа {a₀,a_г), то для сложности по числу делений будем иметь

T_Е{a_г) = шах C_Е(a₀, a) s= 2А(a_х) - 1 = 2Llog_? aj + 2 - 1 «S 2 logo a_г + 1.

Доказанное нами можно переформулировать так:

Если рассматривать a_г как размер входа a₀, a_г алгоритма Евкли­да, то для сложности T_Е(a_х) по числу делений выполнено неравенство

T_E(a₁)^21og₂a₁ + l. (9.6)

Эта же оценка имеет место и при рассмотрении двух параметров a₀, a_г размера входа.

Для достаточно больших a_г верхняя оценка (9.6) существенно луч­ше, чем T_Е{a_г) s= a_г. (Несколько более точная, чем (9.6), оценка дается в задаче 52.)

Рассматривая далее оценки сложности по числу делений алгорит­ма Евклида, мы будем использовать значение a_г в качестве размера входа (значение a₀ может быть очень большим в сравнении с a_ъ но первое же деление с остатком приведет к a_г,a₂, где a₂ <a_г).

Известно, что алгоритм Евклида допускает разнообразные обоб­щения и расширения. Прежде всего, вместе с нод(a₀, a_г) можно на­ходить целые s, t такие, что

sa₀ + ta₁ = HOfl(a_0ja₁). (9.7)