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

Чтобы это показать, обратимся к (9.1). Пусть уже известны a₀,a_ъ ... ..., a_i , 1 ^ i ^ n - 1, и пусть для них найдены множители s₀, t₀; s_ls t_x; ... ...;si, ti такие, что

s₀a₀ + t₀a_г=a₀, s₁a₀ + t₁a₁=a₁, ..., s_i-₁a₀ + t_i-₁a₁=a_i-₁, s_ia₀ + t_ia₁=a_i.

После выполнения очередного деления с остатком a_i-_г = q_ia_i + a_i+1 имеем a_i+1 = a_i-_x - q_ia_i и

(s_{i -}-q_is_iao + Ct_{i -}-q_it_ia^a^.

Можем положить

s_i+1=s_i-₁-q_is_i, t_i+1 = t_i-₁-q_it_i, i = l,...,n-l; (9.8)

при этом

s₀ = l, t₀ = 0; s₁ = 0, t₁ = l. (9.9)

Решение поставленной задачи дают числа

s = s_n, t = t_n.

В процессе применения этого алгоритма к числам a₀ = 39, a_г = 15 возникают остатки 9, 6, 3, 0 и соответствующие ненулевым остаткам пары множителей суть 1, -2; -1, 3; 2, -5. Имеем 2 · 39 + (-5) ·15 = 3 = = нод(39,15).

Этот алгоритм мы назовем расширенным алгоритмом Евклида и будем его обозначать буквами ЕЕ, от его английского названия extended Euclidean—расширенный евклидов. Каждый шаг расширен­ного алгоритма Евклида содержит три мультипликативных опера­ции— одно деление с остатком и два умножения.

Если рассматривать a_г как размер входа a₀, a_г расширенного алго­ритма Евклида, то для мультипликативной сложности T_ЕЕ{a_г) этого алгоритма имеем T_ш{a_г) s= 6 log₂ a_г + 3.

Расширенный алгоритм Евклида дает возможность решать в це­лых числах линейные уравнения с целыми коэффициентами (см. за­дачу 56), он также играет существенную роль в модулярной арифме­тике (см. § 22).

Если дополнить расширенный алгоритм Евклида еще одним ша­гом, то получатся s_n+1, t_n+1 такие, что

sn+iao + tn+iai = 0. (9.10)

Например, для a₀ = 39, a_г = 15 имеем s₅ = -5, t₅ = 13. Легко доказать, что

| si|^|s₂|^|s₃|, |ti|^|t₂|<|t₃L (9.11)

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

и при п>2

|s₃|<|s₄|<...<|s_n+1|, |t₃|<|t₄|<...<|t_n+1|. (9.12)

Несколько труднее, но также возможно доказать, что \s_t | и \t_t | взаим­но просты при i = 1, 2,..., п + 1 (см. задачу 57). Из (9.10) и взаимной простоты s_n+1 и t_n+1 следует

lsn+1l= нод(а₀,_а1), l^f"+1l= нод(а₀,_а1).

Вместе с (9.11), (9.12) это дает нам

IsJsSd1, \t_n\<a₀. (9.13)

Эти неравенства пригодятся нам в дальнейшем.

Пример 9.2. Бинарный поиск места (т. е. значения р, 1 ^ р ^ ^ п + 1,—как объяснено в приложении A) элемента у в упорядочен­ном массиве из п элементов х₁ < х₂ < ... < х_п:

р :=1; q :=п + 1; while p<q do

r:= I ^-^ I ; if x_r<y then p:=r + 1 else q:=r fi od

Обозначим этот алгоритм буквами BS от его английского названия binary search—бинарный поиск. Будем считать число элементов сег­мента массива длиной этого сегмента (при рассмотрении задач сор­тировки и поиска мы называем сегментом массива любую упорядо­ченную часть x_s < x_s+1 < ... < x_t_₁ < x_t данного массива). Легко видеть,

что от сегмента длины к мы переходим к сегменту длины 2 или

2 — 1. Это говорит о том, что с каждым шагом алгоритма функция L(fc) = A(fc), где положительное к является длиной сегмента, рассмат­риваемого на данном шаге, убывает по крайней мере на единицу, пока не приходим к сегменту, содержащему один элемент, после че­го еще одно сравнение полностью решает задачу. Отсюда сложность бинарного поиска не превосходит A(n) = Llog₂ п\ + 1. Мы видим так­же, что если у меньше минимального элемента рассматриваемого сегмента длины к > 1, то длина сегмента на следующем шаге будет

равна \-2\. Поэтому если изначально у <х₁, то в ходе бинарного по­иска будут рассматриваться сегменты длины

^п

l-l 2

2 , 2

n,₂ i2^,...,1