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

89

Для получения простой асимптотической оценки Т_в(п) воспользуемся формулой Стирлинга п\ ~п^пе-^п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! = nlog₂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) = nlog₂n + 0(n), (10.13)

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

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

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

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

Если выполнение циклического (итерационного) алгоритма не завер­шается для некоторого входа 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 не обязательно должны содержать явные упоминания порядков на множествах, хотя введение некоторых порядков пол­ностью проясняет ситуацию.)