- •Глава 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
§ 1. Затраты алгоритма для данного входа
11
тов
(операций
обмена
<->),
то
оно
колеблется
от
0 до
n(n2
1}.
Эта
сортировка
далее
будет
обозначаться
буквой
I,
от
английского
слова
insert—вставка.
В этих примерах уже фактически сказано, что считается размером входа и затратами. В примере 1.1 размер входа — целое неотрицательное n—это порядок матриц. В примере 1.2 размер входа — само входное число (сам вход) n. В примерах 1.1, 1.2 количество исследуемых операций однозначно определяется по n. Столь жесткая зависимость затрат от размера входа может и не иметь места, как это следует из примера 1.3, где размер входа — это длина n массива. В связи с этим примером остановимся пока на операциях сравнения.
Количество
сравнений
n(n~1),
требуемое
в
худшем
случае,
характеризует
рассматриваемый
алгоритм
среди
всех
алгоритмов
сортировки
как
«имеющий
квадратичную
сложность».
Для
придания
этим
словам
точного
смысла
должно
быть,
прежде
всего,
определено
само
понятие
сложности.
Определение 1.1. Пусть на возможных входах x алгоритма A определена неотрицательная числовая функция ||x|| (размер входа). Пусть также определены целочисленные неотрицательные функции CA(x), CA(x) временных и пространственных затрат алгоритма A. Тогда временной и пространственной сложностями A называются функции числового аргумента
TAЛn) = шах CTЛx), SJn) = maxCSAx) (1.2)
11x11=n 1x1 = n
(областью изменения n как аргумента функций TA{n) и SA{n) является множество значений размера || • ||). Более полно каждая такая сложность именуется сложностью в худшем случае.
Вместо TA{n),SA{n) мы иногда будем писать просто T{n),S{n), если ясно, о каком алгоритме идет речь.
Два примечания к определению 1.1.
1) Значение CAT{x) есть в подавляющем большинстве случаев число каких-то операций, а CSA{x)—число хранимых величин какого-то типа, поэтому предположение о целочисленности значений этих функций вполне естественно. Без этого предположения в (1.2) пришлось
тируемых массивов считаются попарно различными. Если не оговорено противное, то речь всегда идет о сортировке по возрастанию. Размером входа каждой из сортировок мы без специального упоминания считаем число n элементов массива.
12 Глава 1. Сложности алгоритмов как функции числовых аргументов
бы использовать sup вместо max, что сделало бы многие рассуждения о сложности более тяжеловесными.
2) Видимо, вместо «сложность в худшем случае» правильнее было бы сказать «сложность как затраты в худшем случае», но такова принятая здесь терминология. Мы пока (до § 5) не рассматриваем сложность в среднем, и поэтому, не опасаясь путаницы, будем называть сложность в худшем случае просто сложностью.
Вернемся к алгоритмам MM, TD, I из примеров 1.1, 1.2, 1.3. Рассмотрим вначале временные сложности Tмм(n), TTD(n), T(n). Получаем Tмм(n) = n3 и T^n) = n(n-1). Для TTD(n) у нас нет столь простой формулы. Заметим, например, что для значений n от 111 до 120 мы имеем
n: 111 112 113 114 115 116 117 118 119 120 TTD(n): 2 19 14 12 16 1
Изменение этой функции при n -> оо можно охарактеризовать так: для любых n значение этой функции не превосходит LanJ - 1, и найдутся сколь угодно большие n, для которых ее значение равно L-s/nJ-L
В примерах 1.2 и 1.3 не возникает необходимости в хранении больших объемов величин сверх объема входа (сортировка простыми вставками не требует дополнительного массива). Дополнительная память, если и нужна, — это несколько дополнительных переменных (ячеек), используемых алгоритмом.
Поэтому можно считать, что S^n)S^n) ограничены константами. В примере 1.1 нам требуется дополнительная матрица, в которой будет формироваться результат; имеем SMM(n) = n2.
Во всех этих примерах мы, как легко заметить, принимаем во внимание лишь часть затрат и в соответствии с этим определяем сложность алгоритма. В примере 1.1 учитывались только умножения как более дорогие (доминирующие по затратности) операции. В примере 1.3 мы рассматриваем либо сравнения, либо обмены. И во всех примерах мы игнорировали затраты по выполнению управляющих операторов, хотя, скажем, при выполнении простейшего оператора цикла
for i = l to n do ... od
тратится время на изменение параметра цикла, проверку условия продолжения цикла и т.д.
Обычно в таких ситуациях считается, что мы учитываем основную часть затрат для худшего случая. Если пытаться точно подсчитывать