- •Глава 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
§ 15. Оптимальные алгоритмы
111
ства а = 0, b = c = 1, d = n-2. После первого сравнения на протяжении всего выполнения алгоритма постоянно будут иметь место неравенства Ъ^1,с^1.
Все сравнения, совершаемые при выполнении алгоритма V, можно разбить на типы, обозначаемые AA,AB,AC,AD, BB,BC,BD,CC, CD,DD, например: сравнение принадлежит типу АВ, если один из сравниваемых элементов берется из А, другой—из В, и т. д. Исходя из этого, можно выписать все возможные изменения четверки (а, Ь, с, d) под действием сравнений разных типов:
1,b,c,d + 1), 1,b,c,d + 1), 1,b,c + 1,d),
АА: (а-2, b + 1,c + 1,d), АВ: (a-1,b,c + 1,d)|(a АС: (а-1, b + 1,c,d)|(a AD: (а - 1, Ъ + 1, с, d) | (а
BB: (a, b - 1, c, d + 1), BC : (a, b - 1, c - 1, d + 2) | (a, b, c, d), BD: (a, b - 1, c, d + 1) | (a, b, c, d), CC : (a, b, c - 1, d + 1), CD: (a, b, c - 1, d + 1) | (a, b, c, d), DD: (a, b, c, d) (вертикальная черточка здесь означает «или»). Рассмотрим функцию
= -2а + Ъ + с 3
2. Для начальной и конечной стадий имеем
L(a, b, c, d)
n —
2)=0 соответственно.
I(n,0,0,0) = 32n-2 и 1(0,1,1,
Каждое сравнение типов AA, BB, CC понижает значение L на 1, т.е. дает ∆L =-1. Выпишем все возможные значения ∆L при выполнении сравнений различных типов:
-1, — 1 | 0,
-32i-12,
—2 | 0,
_1 2, 0.
AA, BB, CC : BD, CD :
AB, AC : BC : AD : DD :
Сравнения, относящиеся к типам AB, AC, BC, могут приводить к ∆L <-1, но это не может быть гарантировано никаким специальным выбором элементов из соответствующих множеств четверки
112 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы
(A, B, C, D), даже если принимать во внимание результаты всех сравнений, в которые были вовлечены конкретные элементы этих множеств. Например, сравнение типа AB в том случае, когда выбранный элемент из A оказывается больше выбранного элемента из B, преобразует (a, b, c, d) в (a - 1, b,c,d + 1), что дает ДL < -1. Но результаты предшествующих сравнений не дают оснований для отметания возможности того, что выбранный элемент из B равен шах{x1, x2, •••, xn} (ибо этот элемент оказался большим во всех сравнениях, в которые
он был вовлечен). Но тогда будет выполнено ДL = -12. Аналогичным образом дело обстоит для сравнений, принадлежащих типам AC, BC. Поэтому, рассматривая поведение алгоритма V в худшем случае, надо считать, что на всех этапах ДL ^ - 1. Но тогда для достижения равенства L(a, b, c, d) = 0 потребуется не менее \L(n, 0, 0, 0)1 сравнений. Это значит, что общее число сравнений в худшем случае не меньше,
чем -n - 2. □
Представленный в приложении A алгоритм одновременного поиска наибольшего и наименьшего элементов массива, требующий в худшем
случае не более -2 - 2 сравнений, является оптимальнымг.
Наряду с алгоритмами поиска наименьшего элемента, бинарного поиска места элемента в упорядоченном массиве и алгоритма одновременного поиска наибольшего и наименьшего элементов массива примером оптимального алгоритма может служить алгоритм («схема») Горнера вычисления значения полинома в данной точке (см. приложение D).
Для произвольного класса .s4 оптимальный алгоритм может и не существовать: если, например, .s4 содержит ровно два алгоритма, A1,A2, и при этом A1 имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечетных, а A2 — наоборот, то, очевидно, ни A1, ни A2 не будут оптимальными в .s4. Ясно, что если оптимальные алгоритмы в классе .s4 существуют, то их сложности совпадают: из неравенств TA (n) ^ TA (n) и TA 2 (n)^TA 1 (n) следует, что TA 1 (n) = TA 2 (n). Несколько более содер-жательный пример можно найти в задаче 76.
В отличие от поиска наименьшего элемента, поиска места в упорядоченном массиве и одновременного поиска наибольшего и наи-
1 Этот алгоритм и идея использования четверок ( A, B, C, D) в доказательстве его оптимальности были предложены И. Полом в [56], но при этом убывающие функции в его доказательстве не привлекались, из-за чего потребовались дополнительные словесные мотивации.