- •Глава 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. Затраты алгоритма для данного входа
13
все, не упуская ничего, то получение и обоснование оценки сложности заурядного алгоритма может превратиться в очень тяжелую работу. Принимая решение о том, в чем измеряются временные затраты, мы разделяем важное и неважное. Разумеется, при этом необходима осторожность, без которой к разряду неучитываемых «дешевых» операций могут быть отнесены такие, на выполнение которых в реальных вычислениях уйдет существенное время из-за их огромного количества.
Отметим еще, что, вообще говоря, время выполнения операции зависит от размеров ее операндов, это относится и к арифметическим операциям, и к операции сравнения (например, длинные числа сравнивать труднее, чем короткие и т.д.). Аналогично дело обстоит с пространственными затратами и соответственно с пространственной сложностью; здесь, прежде чем находить сложность, надо решить, что является «единицей хранения»: скажем, при умножении двух матриц мы можем получить матрицу с элементами, которые записываются более длинно, чем элементы исходных матриц. Однако довольно часто считается, что результат операции всегда умещается в одной ячейке.
Иногда приходится отвлекаться от того, что десятичная или двоичная запись иррационального числа не может быть размещена в ячейке какого-либо устройства. Более того, в теории алгебраической сложности как разделе алгебрыг рассматривают, например, алгоритмы, применимые к элементам произвольного абстрактного кольца или поля, и вопрос о представлении этих элементов в реальном компьютере или в абстрактной машине не обсуждается вообще.
Определение 1.2. Пусть функция СТА(х) в определении 1.1 отражает затраты на выполнение лишь какого-то одного типа операций в предположении, что все эти операции требуют одинакового времени выполнения, не зависящего от вида и размера операндов, и это время равно 1. Тогда соответствующая функция ТА(п)—это сложность по числу операций рассматриваемого типа. Привлечение в качестве Сд(х) функции, отражающей только количество хранимых дополнительных величин того или иного фиксированного типа, приводит к пространственной сложности SA(n) по числу величин рассматриваемого типа.
Такую сложность называют алгебраической сложностью по числу операций или числу величин рассматриваемого типа, подчерки-
См., например, [25].
14 Глава 1. Сложности алгоритмов как функции числовых аргументов
вая этим предположение о равнозатратности всех рассматриваемых операций и равнообъемности всех учитываемых величин. Алгебраическую сложность арифметических алгоритмов по числу умножений и делений называют мультипликативной сложностью. Из основных арифметических операций умножение и деление являются наиболее дорогими, и при рассмотрении арифметических алгоритмов часто интересуются именно (алгебраической) мультипликативной сложностью.
Несколько позднее мы будем говорить о битовой сложности, которая позволяет принимать в расчет различие в размерах операндов и рассматривать при нахождении сложности непохожие операции, сопоставляя их затратность на битовом уровне.
Формулы (1.2) вновь заставляют вспомнить о важности понятия размера входа. В силу разных причин не всегда этот размер легко и естественно может быть введен так, что сложность алгоритма возрастает при увеличении размера входа. Но, по крайней мере, функция || • || должна обеспечивать определенность значений TA{n), SA{n) для всех достаточно больших n — иначе было бы невозможно говорить о поведении TA{n), SA{n) при n—> <х>.
Заведомо неудачный размер входа — это, скажем, число строк n данной матрицы, если речь идет об алгоритмах вычисления произведения всех элементов и если матрица не обязательно является квадратной: при выбранном таким образом размере входа мы имеем тождественное равенство TA{n) = оо для сложности по числу умножений любого такого алгоритма A, так как при фиксированном числе строк число столбцов и число элементов могут быть сколь угодно большими.
Другие возможные осложнения, вызванные неудачным выбором размера входа, будут обсуждаться в § 13.
Достаточно очевидно, что если алгоритм A состоит в последовательном (друг за другом) выполнении алгоритмов U и V, то мы, вообще говоря, не можем утверждать, что TA{n) = TU{n) + TV{n), так как, например, размер входа алгоритма U может существенно отличаться, как в большую, так и в меньшую сторону, от размера его выхода.
Пусть A и B—некоторые алгоритмы. Как можно заметить, из выполнения для всех n неравенства TA{n) < TB{n) не следует, что CTА{x) < <CB(x) для всех возможных входов x (достаточно вспомнить сортировку слияниями и пузырьковую сортировку; последняя выполняется быстрее первой, коль скоро массив задан уже в упорядоченном виде). Аналогично дело обстоит с пространственными сложностью и затратами.