- •Глава 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. Сложность в среднем
и возможно дальнейшее упрощение выражения для сложности:
m -1 m -2
k=i l=о
Если рассматривать m = А(n) как размер входа бинарного алгоритма вычисления an, neN+, то сложность в среднем по числу умножений для этого алгоритма есть |(m - 1).
Таким образом, при больших m сложность в среднем бинарного алгоритма возведения в степень приблизительно равна трем четвертым сложности в худшем случае.
Анализ сложности в среднем для широкого ряда арифметических алгоритмов опирается на асимптотический закон распределения простых чисел, который мы приведем без доказательства.
Асимптотический закон распределения простых чисел. Для
функции п(n), значение которой равно количеству простых чисел, меньших данного натурального n, справедливо асимптотическое равенство
я(n)~тn-. (5.3)
Inn
Как следствие, вероятность того, что при выборе «наугад» одного
из целых чисел 1,2, ...,n попадется простое число, асимптотически
1 1 равна 1—.х
шn
Пример 5.2. Вновь вернемся к алгоритму пробных делений, предназначенному для распознавания простоты данного n ^ 2 (примеры 1.2, 4.1). Будем рассматривать в качестве размера входа битовую
1 Предположение о справедливости этого закона распределения простых чисел высказывалось, в частности, Гауссом и Лежандром. Впоследствии в 1850 г. Чебышевым было доказано, что для некоторых констант c и C
c—<к{n)<C — Inn Inn
для всех достаточно больших n, и, более того, им было установлено, что можно положить C = 1,10555, c = 0,92129. Асимптотическое равенство (5.3) было полностью доказано в 1896 г. независимо Ж.Адамаром и Ш. Валле Пуссеном. «После доказательства неравенств Чебышева в 1850 г. речь шла, казалось бы, только о более точном нахождении и сближении постоянных c и C. Однако асимптотический закон распределения простых чисел был доказан лишь полвека спустя, в самом конце XIX века, на основании совершенно новых идей, предложенных Риманом...» [39]. В [39, гл. V] приводится
элементарное доказательство неравенств Чебышева для C = 6 и c = -. Полное доказа-
тельство асимптотического закона имеется, например, в [16].
§ 5. Понятие сложности в среднем
45
длину т данного числа. На первый взгляд сложность в среднем этого алгоритма могла бы оказаться существенно меньшей, чем сложность в худшем случае, так как для многих входов затраты совсем невелики. Например, для четных входов достаточно одного деления и т. д. Для сложности в худшем случае по числу делений нами была установлена экспоненциальная оценка в(2т/'2). Существует ли deN такое, что сложность в среднем алгоритма пробных делений как функция от т допускает оценку 0{md)? Мы видим, что для довольно обширного множества входов размера т алгоритм пробных делений работает быстро, и предположение, что для сложности в среднем существует такое число d, выглядит правдоподобным. На самом деле все обстоит не так, потому что среди всех натуральных чисел доля простых (для которых алгоритм пробных делений работает долго) достаточно велика. Оценка количества V{m) простых среди чисел
2т-г ^п<2т
может быть получена из приведенной выше теоремы о распределении простых чисел: воспользовавшись тем, что
от
7г(2т)
~ .
—,
т—>оо5
а
также
равенством
V{m)
=
п{2т)
- п{2т-г),
получим
Теперь уже экспоненциальность роста сложности в среднем алгоритма пробных делений выводится легко. Обозначим через D{n) количество делений, требующееся алгоритму пробных делений применительно к натуральному числу п. Для любого простого р ^ ^ 2т-г, т^7, выполнено D{p) > 2т1^х (в самом деле, D{p) = LVpJ - 1 Z L2(m-1)/2J - 1 > 2&"-«/2 - 2, и при т ^ 7 выполнено
;m-l)/2 ПШ/2-1 ТЛ
2т — 1
на ^гт 2 D{n). При т ^ 7 мы имеем
2(m 1)/2 - 2 ^ 2т12 г). Интересующая нас сложность в среднем рав-1
= 2Г71-1
2т-1
1
Т. |
D(n)^ |
1 ГП-1 |
|
Т. |
=2т-1 |
|
|
2m p |
-Чр<2т — простое |
2т_1 „,! D{p)^V{m)2-ml2. (5.5)
2ГП-1
Учитывая (5.4), находим, что последняя величина при т —»оо асимптотически равна
1 от/2
(21п2)т '
46