Завершимость работы алгоритма

Л Л

П

Ф

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 2 n _! F 2 n _2 F 2 n _3 F 2 n -2

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

М = \r: r=—, a _n = a i, a i +1,... к а ₁ ^и 1 1

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

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

отрезка Φ_п, т. е. — ^ ■= ------ =—, или, что то же самое, а_г ^ F _{2 n} _i F _{2 n} . Пусть

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

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

откуда

W2 N +1 < СФ^4Ы,

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

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

с.

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

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

делений соотношение 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^ln a ₁+ O (l). (10.9)

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

T _E(a ₁) > i^ln a ₁+_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 отрезок Ф„ не содержит чисел вида —, m eN⁺); если 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(a j) ~logj, а_ь насколько известно автору, не доказано
и не опровергнуто (2008 г.).

§ 11. Завершимостъ работы алгоритма

Для получения простой асимптотической оценки Т_в(п) воспользуемся формулой Стирлинга п\ ~п^пе-^п4Ъкп, или, что то же самое,

n\ = nⁿe-ⁿ\[b^i{l+o{l)), которая после логарифмирования принимает вид

log₂ п\ = п log₂ п-п log₂ е + \ log₂ п + \ log₂ л + \ + о(1)

(принято во внимание, что log₂(l+ о(1)) = о(1)). Так как l < log₂ e< < 2, то

п log₂ п - 2п < log₂ п\<п log₂ п-п (10.12)

для всех достаточно больших п; в частности, это означает, что

log₂ n! = n log₂ n + 0(n).

Имеем

Y, Tlog₂ fcl =2 log₂ k + 0(n) = log₂ n! + 0(n) = n log₂ n + 0(n).

k=l k=l

Отсюда получаем оценку

T _B(n) = n log₂ n + 0(n), (10.13)

из которой следует, в частности, что Т_в(п) ~ п log₂ п.

Таким образом, тщательный анализ суммы (10.11) не приводит к су­щественно лучшей, чем (9.14), оценке, но зато дает асимптотику Т_в(,п).

В § 14 будет показано, что из того, что сложность по числу сравне­ний некоторой сортировки не превосходит n log₂ n + cn, где с—неко­торая константа, следует, что эта сложность есть n log₂ n + 0(n). Из этого будет следовать, что для сложности по числу сравнений сорти­ровки фон Неймана выполнено T _vN(n) = n log₂ п + 0{п); мы обознача­ем эту сортировку буквами vN, от фамилии von Neumann.

Если выполнение циклического (итерационного) алгоритма не завер­шается для некоторого входа v, то сложность этого алгоритма не определена для значения аргумента, равного || v ||. Поэтому анализ сложности алгоритма прямо или косвенно включает исследование за-вершимости.

Установление завершимости может быть рассмотрено и как са­мостоятельная задача. Когда функция L подбирается для выяснения зависимости числа шагов алгоритма от размера входа задачи, то при

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

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

Пример 11.1. Алгоритм, заданный оператором цикла

while n> 3 do

if 2 | n then n:= ₂ + 1 else n:= n + 1 f i od

(запись 2 | n означает, что n делится на 2) завершает свою работу для любого натурального п. Для доказательства достаточно рассмот­реть функцию п - (-1)" и убедиться в ее убывании при п > 3 в ходе выполнения алгоритма.

Пример 11.2. Если п — данное неотрицательное целое число, то завершимость выполнения алгоритма

s:=0;

for i = 1 to n do s: = s + ¹ od

очевидна—выполнение оператора цикла завершится после п шагов; легко видеть, что при выполнении этого оператора значение L(n, i) = = n - i убывает, оставаясь при этом неотрицательным целым.

В доказательствах завершимости, основанных на подборе подхо­дящей убывающей целочисленной функции, используется следующее свойство множества N неотрицательных целых чисел:

Не существует бесконечной убывающей последовательности п ₀ > >п₁> п₂>... элементов множества N.

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

¹ Вместо сложных примеров, мы адресуем читателя к задачам 67, 68, заимствован­ным из [9, разд. 2.3]. В книге [9] кроме двух названных задач содержится интересный и полезный материал о частично упорядоченных множествах и некоторых специаль­ных типах таких множеств. (Решения задач 67, 68 не обязательно должны содержать явные упоминания порядков на множествах, хотя введение некоторых порядков пол­ностью проясняет ситуацию.)

§ 11. Завершимостъ работы алгоритма

Установление завершимости выполнения алгоритма иногда ока­зывается очень трудной задачей.

Пример 11.3. Завершимость для любого натурального п выполне­ния алгоритма

while п > 1 do

if 2\п then n:=^ else n:=3 n + 1 fi od

не доказана и не опровергнута по сей день, хотя на это направлялись серьезные усилия (см. [53]).

В случае рандомизированных алгоритмов мы сталкиваемся (см. ниже пример 11.4 и первую часть примера 11.5) с возможностью того, что алгоритм завершается с вероятностью 1, но математическое ожидание времени от начала выполнения до полного завершения алгоритма бесконечно. Поэтому утверждения о завершимости воз­можны в двух формах: завершимость с вероятностью 1 и конечность ожидаемого времени выполнения. Вторая форма является, вообще говоря, более сильной.

Пример 11.4. В теории вероятностей подробно рассматривается задача о блуждании частицы по прямой: за один шаг частица пе­редвигается на 1 вправо или на то же расстояние влево, направле­ние же движения на каждом шаге выбирается случайно, вероятно­сти выбора каждого из направлений одинаковы и равны ¹₂. Пусть в начальный момент частица находится в точке 0, и на прямой от­мечена некоторая точка т с целой координатой. Доказывается, что с вероятностью 1 частица через некоторое время попадает в точку т. Попытаемся теперь вычислить математическое ожидание а времени (общего числа шагов), которое потребуется для достижения точки т. Легко убедиться, что уже в случае т = ±1 это среднее бесконечно. Пусть, например, т = 1. Используем формулу полного математиче­ского ожидания: если шаг сделан вправо, то за этот один шаг мы достигаем цели, если же шаг сделан влево, то придется дождаться момента, когда частица вернется в точку 0 и тем самым повторится начальная ситуация:

а = 1-¹₂ + 2а-₂¹.

Если бы а было конечным, это бы дало 0 = ¹₂. Поэтому среднее бес­конечно.

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

Рассмотрим с этой точки зрения задачу 17. Итак, путник столкнул­ся со стеной, простирающейся бесконечно в обе стороны. Имеется дверь в этой стене, но путник не знает ни расстояния до двери, ни направления к ней. Если путник использует алгоритм поиска двери, состоящий в бросании перед каждым шагом монеты для определения направления (вправо или влево) этого шага, то он с вероятностью 1 найдет дверь, но математическое ожидание числа шагов равно бес­конечности, коль скоро в начальный момент путник не стоит прямо перед дверью. Иными словами, если p_k (k ^ 1) есть вероятность того, что после k шагов путник впервые окажется перед дверью, то

Дата добавления: 2014-01-11