- •Глава 1
- •§ 1. Затраты алгоритма для данного входа, алгебраическая сложность
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 3. Асимптотические оценки (два примера) 23
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •Глава 2
- •§ 5. Понятие сложности в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства.
- •§ 6. Сортировка и конечные вероятностные пространства 47
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 49
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 51
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •§ 7. Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем 55
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 3
- •§ 9. Функции, убывающие по ходу выполнения алгоритма
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 75
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 77
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 79
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 81
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимость работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 97
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 99
- •Глава 4
- •§ 14. Понятие нижней границы сложности
- •§ 14. Понятие нижней границы сложности
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 16. Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности
- •§ 16. Асимптотические нижние границы
- •§ 16. Асимптотические нижние границы
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем 125
- •§ 18. Нижние границы сложности рандомизированных алгоритмов. Принцип Яо
- •§18. Нижние границы сложности рандомизированных алгоритмов 127
- •Глава 5
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •Глава 5. Битовая сложность
- •Глава 6
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 163
- •§ 25. Об одном классе нелинейных рекуррентных соотношений
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 165
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 167
- •§26. Асимптотические оценки решений рекуррентных неравенств 169
- •§ 26. Асимптотические оценки решений рекуррентных неравенств
- •§ 26. Асимптотические оценки решений рекуррентных неравенств 171
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 173
- •§ 27. Добавление нулей 175
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 179
- •Глава 7 Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности
- •§ 29. Линейная сводимость и нижние границы сложности 191
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности 193
- •Глава 7. Сводимость
- •§ 30. Классы PиNp
- •§ 30. Классы р и np
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 201
- •§ 31. Существование задач распознавания, не принадлежащих р. Связь моделей мт и рам
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 203
- •Глава 7. Сводимость
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 1. Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае
- •119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-74-83
§ 11. Завершимостъ работы алгоритма
89
Для получения простой асимптотической оценки Тв(п) воспользуемся формулой Стирлинга п\ ~ппе-п4Ъкп, или, что то же самое,
n\ = nne-n\[b^i{l+o{l)), которая после логарифмирования принимает вид
log2 п\ = п log2 п-п log2 е + \ log2 п + \ log2 л + \ + о(1)
(принято во внимание, что log2(l+ о(1)) = о(1)). Так как l<log2e< <2, то
п log2 п - 2п < log2 п\<п log2 п-п (10.12)
для всех достаточно больших п; в частности, это означает, что
log2n! = nlog2n + 0(n).
Имеем
Л Л
Y, Tlog2 fcl =2 log2 k + 0(n) = log2 n! + 0(n) = n log2 n + 0(n).
k=l k=l
Отсюда получаем оценку
TB(n) = nlog2n + 0(n), (10.13)
из которой следует, в частности, что Тв(п) ~ п log2 п.
Таким образом, тщательный анализ суммы (10.11) не приводит к существенно лучшей, чем (9.14), оценке, но зато дает асимптотику Тв(,п).
В § 14 будет показано, что из того, что сложность по числу сравнений некоторой сортировки не превосходит nlog2n + cn, где с—некоторая константа, следует, что эта сложность есть nlog2n + 0(n). Из этого будет следовать, что для сложности по числу сравнений сортировки фон Неймана выполнено TvN(n) = n log2 п + 0{п); мы обозначаем эту сортировку буквами vN, от фамилии von Neumann.
§ 11. Завершимость работы алгоритма
Если выполнение циклического (итерационного) алгоритма не завершается для некоторого входа v, то сложность этого алгоритма не определена для значения аргумента, равного ||v||. Поэтому анализ сложности алгоритма прямо или косвенно включает исследование за-вершимости.
Установление завершимости может быть рассмотрено и как самостоятельная задача. Когда функция L подбирается для выяснения зависимости числа шагов алгоритма от размера входа задачи, то при
90 Глава 3. Оценивание числа шагов (итераций) алгоритма
наличии выбора более предпочтительной является функция с медленным ростом (имеется в виду рост при увеличении размера входа); даже если при этом усложняется доказательство того, что L обладает всеми нужными свойствами, мы зато получаем более точную оценку числа шагов алгоритма. Но иногда речь может идти только о доказательстве завершимости работы алгоритма — тогда характер роста функции L отходит на второй план. То, что выполнение алгоритма Евклида завершается, было доказано в самом начале обсуждения этого алгоритма без обращения к функциям с логарифмическим ростом.
Пример 11.1. Алгоритм, заданный оператором цикла
while n>3 do
if 2 | n then n := 2 + 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 + 1 od
очевидна—выполнение оператора цикла завершится после п шагов; легко видеть, что при выполнении этого оператора значение L(n, i) = = n - i убывает, оставаясь при этом неотрицательным целым.
В доказательствах завершимости, основанных на подборе подходящей убывающей целочисленной функции, используется следующее свойство множества N неотрицательных целых чисел:
Не существует бесконечной убывающей последовательности п0 > >п1> п2> ... элементов множества N.
Имеются и другие примеры (частично) упорядоченных множеств с этим свойством, и соответствующие порядки используются для доказательства завершимости выполнения алгоритмовг.
1 Вместо сложных примеров, мы адресуем читателя к задачам 67, 68, заимствованным из [9, разд. 2.3]. В книге [9] кроме двух названных задач содержится интересный и полезный материал о частично упорядоченных множествах и некоторых специальных типах таких множеств. (Решения задач 67, 68 не обязательно должны содержать явные упоминания порядков на множествах, хотя введение некоторых порядков полностью проясняет ситуацию.)