- •Глава 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
§ 2. Асимптотические оценки (формализм)
Для характеристики роста сложности по числу сравнений сортировки простыми вставками первого и второго типа мы можем использовать известный из математического анализа символ O и написать T{n) = O{n2) (здесь и далее n-> оо). Мы можем также выделить главные по росту слагаемые в (1.3):
T{n) = n2 + O{n), T 2 (n) = |n2 + O(n), (2.1)
хотя в этом и нет ощутимого практического смысла в силу простоты функций T] (n), T]2(n). В то же время, как это хорошо известно, асимптотическая формула f{n) = O{g{n)) является удобным средством оценивания нетривиально устроенной функции f(n) с помощью более простой функции g(n); столь же полезными оказываются и оценки вида f(n) = o(g(n)). Но когда мы говорим, что сортировка выбором, пузырьковая сортировка и сортировка простыми вставками имеют квадратичные сложности, мы имеем в виду не только то, что соответствующие сложности допускают оценку O{n2), но что эти сложности являются величинами порядка n2; в математическом анализе это иногда записывается как T{n)~n2, где T{n)— рассматриваемая функция, в данном случае — сложность. В последние годы в теории сложности алгоритмов вместо f{n)~g{n) стали писать f(n) = 6(g(n)).
Определение 2.1. Функции f(n) и g{n) имеют одинаковый порядок (пишут f(n) = 6(g(n))) тогда и только тогда, когда найдутся положительные cъ c2, N такие, что неравенства
cilg(n)|sS|f(n)|sSc2|g(n)| (2.2)
выполнены для всех n>N.
Без труда проверяется, что отношение «иметь одинаковый порядок» является отношением эквивалентности на множестве функций,
§ 2. Асимптотические оценки (формализм)
19
определенных для всех достаточно больших значений п (в нашем случае эти значения целые). Несимметричность записи /(n) = 6(g(n)) в сравнении с записью /(n) xg(n) (/(п) и g{n) как бы не равноправны в первой записи, хотя имеем дело с отношением эквивалентности) объясняется тем, что обычно эту запись используют, когда g{n) проще, чем /(п).
Итак, для сложности Т{п) по числу сравнений для любого из упомянутых алгоритмов сортировки мы имеем Г(п) = 6(п2). Это более сильное утверждение, чем Т{п) = 0{п2), так как Т{п) = 0{п2) является лишь асимптотической верхней оценкой: в соответствии с известным из математического анализа определением
f{n) = 0{g{n)) <^> 3C;N>0 Vn>N |/(n)|sSc|g(n)|,
например, n = 0{п2), но неверно, что п = в(п2). Здесь и далее, пользуясь кванторами 3, V, мы записываем связываемые ими переменные, равно как и условия, определяющие множества значений этих переменных, в виде индексных выражений при кванторах. Это часто позволяет обходиться без дополнительных скобок и облегчает чтение формул.
Иногда бывают полезными нижние асимптотические оценки.
Определение 2.2. Соотношение /(n) = fi(g(n)) имеет место тогда и только тогда, когда найдутся положительные с, JV такие, что для всех n>N выполнено |/(n)|^c|g(n)|.
Следующее предложение выводится из определений символов О, П и в.
Предложение 2.1. Соотношение /(n) = 6(g(n)) имеет место тогда и только тогда, когда одновременно /(п) = 0(g(n)) и /(n) = fi(g(n)); помимо этого, /(п) = ОДп)) тогда и только тогда, когда g{n) = = 0(/(п)).
Если размер входа является целым положительным числом, то возникающие функции являются последовательностями. Для единообразия мы, как правило, будем говорить о функциях, подразумевая, но не упоминая специально, что каждая такая функция определена лишь для целых положительных значений аргумента (возможно даже, только для достаточно больших целых положительных значений аргумента). Итак, при п->оо оценки вида /(n) = A(g(n)), где Л —один из символов Г2, О, в, предполагают, что функции f{n),g{n) определены для всех достаточно больших п. Соответствующее неравенство из
20 Глава 1. Сложности алгоритмов как функции числовых аргументов
числа
\f{n)\^c1\g{n)\, |f(n)|sSc2|g(n)|, cilgCnOlsSlfCnOlsScalgCnOI (2.3)
тоже, в соответствии с определением, должно выполняться лишь для n, больших некоторого N. Заметим, однако, что если f(n) и g{n) определены для всех nsN+ и принимают при 1 ^ n ^ N ненулевые значения, то можно считать, что соответствующее неравенство из перечисленных в (2.3) выполняется для всех n, так как, положив
• 1f(n)1 1f(n)1
m= mm т-7-77, M= max т-т-тт,
IsCnsCN \g(n)\ IsCnsCN \g(n)\
мы можем заменить cъc2 в (2.3) на c[ = тт{cъm}, c'2 = тт{c2,M}. Это замечание в некоторых случаях будет для нас полезным.
Вернемся к примеру 1.2. Для сложности алгоритма пробных делений было бы ошибкой утверждать, что его сложность по числу делений есть 6(лn)- Но оценка O(лn), разумеется, верна и, более того, является точной в смысле следующего определения.
Определение 2.3. Если имеет место оценка f(n) = O(g(n)), то она называется точной, коль скоро существует неограниченно возрастающая последовательность неотрицательных целых чисел {nk} такая, что для 4>{k) = f{nk), Vk) = g(nk) имеет место у(k) = Qty (k)).
Для упомянутых ip(k) и t/>(k) в силу этого определения и семантики символа в выполнено y>(k) = 6(i/>(k)).
При рассмотрении алгоритма пробных делений для доказательства точности оценки O(лn) можно взять nk равным k-му простому числу, k = 1,2,...
Понятие точности оценки вида f(n) = O(,g(n)) можно определить также с помощью знакомого из математического анализа символа o; напомним, что u(,n) = o(v(_n)) при n—><*>, коль скоро u{n) = a{n)v{n) и lima(n) = 0.
Предложение 2.2. Пусть f{n) = O{g{n)). Эта оценка является точной, если и только если неверно, что f(n) = o(g(n)).
Доказательство. Пусть оценка является точной, и {nj —возрастающая последовательность, о которой говорится в определении 2.3. Тогда существует положительная константа c такая, что \f{nk)\^c\g{nk)\, k = l,2, ..., и соотношение f{n) = o{g{n)) места не имеет. Обратно, если неверно, что f(n) = o(g(n)), то по определению символа o существуют е > 0 и возрастающая последовательность {nk} натуральных чисел такие, что |f(nk) | ^ e|g(nk) |, k = 1, 2, ... Если при