- •Глава 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
§ 16. Асимптотические нижние границы
117
Из этого примера видно, что само свойство оптимальности находится в зависимости от выбора размера входаг.
В следующем примере, касающемся сортировки массивов, рассматривается сложность в худшем случае по числу сравнений.
Пример 16.4. Аналогично тому, как это сделано в примере 16.1, мы получаем, что любая сортировка, сложность которой допускает оценку О (log п!), является оптимальной по порядку сложности. В силу формулы Стирлинга мы имеем п log2 п = 0(log п!), откуда следует, что любая сортировка, сложность которой по числу сравнений допускает оценку 0(n log п), является оптимальной по порядку сложности.
Сортировка бинарными вставками и сортировка фон Неймана являются оптимальными по порядку сложности по числу сравнений.
(Позднее мы установим оценку O(nlogn) и для сложности рекурсивной сортировки слияниями.) Эти сортировки имеют разные сложности как функции от п: например, TvN(5) = 9, Гв(5) = 8. Но, повторим, их сложности являются величинами одного порядка при п—> <х>. Резюмируем наши наблюдения.
Предложение 16.1. Необходимым и достаточным условием оптимальности сортировки по порядку сложности является справедливость оценки O(nlogn) для сложности этой сортировки. Если для некоторой сортировки справедлива оценка O(nlogn), то справедлива и оценка G(nlogn).
Доказательство. Достаточность уже установлена выше. Оставша яся часть доказательства следует, например, из теоремы 16.1 и оп тимальности по порядку сложности сортировки бинарными встав ками. □
Заметим при этом, что для сортировок бинарными вставками и фон Неймана справедливо значительно более сильное утверждение, чем утверждение об их оптимальности по порядку сложности. Для их сложностей и сложности Topt(n) оптимального алгоритма имеет место асимптотическая эквивалентность:
Тв(п) ~ TvN(n) ~ Topt(n) ~ п log2 п ~ log2 п\.
Коснемся нижних границ пространственной сложности алгоритмов сортировки. Если из всех этих алгоритмов выделить класс таких, которые используют для перемещения элементов обмены (<—>), а не присва-
1 Этот пример сообщил автору Е. В. Зима.
118 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы
ивания (:=), то для этого класса единственной нижней границей, если говорить о функциях, принимающих неотрицательные значения, будет тождественно равная нулю функция, так как существуют, например, пузырьковая сортировка, сортировки простыми и бинарными вставками, не использующие дополнительных переменных того типа, к которому относятся элементы сортируемого массива. (То, что требуются переменные для хранения значений индексов элементов, несущественно при изучении алгебраической сложности сортировки.) Алгоритмы, использующие присваивания для перемещения сортируемых элементов, не могут, естественно, обойтись без дополнительного места для хранения хотя бы одной величины того же типа, что и элементы сортируемого массива, и одной из нижних границ будет функция, тождественно равная единице. Если рассматривать все алгоритмы сортировки вместе, то вновь единственная неотрицательная целочисленная граница— это 0. В соответствии с этим определяются как оптимальные, так и оптимальные по порядку сложности алгоритмы.
Для произвольного класса .s4 оптимальный по порядку сложности алгоритм может и не существовать: если .s4 содержит всего два алгоритма Aг,A2 и при этом Aг имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечетных, а A2 — наоборот, то, очевидно, ни Aъ ни A2 не будут оптимальными в .s4 по порядку сложности (представим себе, что TA = = (1 + (-1)n)n, TA2 = (1 - (-1)n)n). В то же время, если допустить, что TA =(2+(-1)nn , TA =(2-(-1)n)n, то TA (n) = е(TA (n)) (обе функ-ции имеют порядок n), и это говорит о возможности существования оптимального по порядку сложности алгоритма при отсутствии оптимального.