- •Глава 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. Сложность в среднем
Это говорит о том, что исследуемая сложность по числу делений
в среднем есть Г2( — 2m/2) и как функция от m эта сложность не мо- m
жет быть оценена как O{md) ни при каком deN.
Определение 5.2. Вещественная неотрицательная функция f(m), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином P{m) с вещественными коэффициентами такой, что f{m)^P{m) для всех meN+. (Очевидно, что мы получим эквивалентное определение, если дополнительно потребуем, чтобы все коэффициенты полинома P{m) были неотрицательными; другие эквивалентные варианты определения: f{m) = O{md) для некоторого deN и f(m) = mO(1).)
Доказанное нами можно сформулировать так:
Пусть в качестве размера входа алгоритма пробных делений, предназначенного для распознавания простоты натурального числа n, привлекается m = А(n). Тогда временные сложности этого алгоритма как в худшем случае, так и в среднем по числу делений не являются полиномиально ограниченными функциями от m.
Краткое обсуждение идеи такого алгоритма распознавания простоты числа, который имеет полиномиально ограниченную сложность в худшем случае (тем самым, разумеется, и в среднем), будет проведено в примере 22.2. При этом речь пойдет не об алгебраической сложности по числу делений, мультипликативной сложности и т. д., а о битовой сложности, что приводит к существенно более сильным утверждениям. До этого в гл. 5 будет детально рассмотрено само понятие битовой сложности.
§ 6. Сортировка и конечные вероятностные пространства.
Применение формулы полного математического ожидания
При рассмотрении сложности в среднем мы, прежде всего, должны превратить каждое из множеств входов, обладающих фиксированным размером, в вероятностное пространство. Проще работать с конечными вероятностными пространствами, но как обходиться такими пространствами, имея дело, например, с алгоритмами сортировки, входом каждого из которых, при фиксированном размере n, может быть любой массив xг,x2, ■■■,xn с попарно различными элементами? Общий принцип заключается в том, что мы разбиваем все имеющие фиксированный размер n входы на некоторые классы, включая в один
§ 6. Сортировка и конечные вероятностные пространства 47
класс входы, неразличимые для данного алгоритма в том смысле, что алгоритм проделывает одну и ту же последовательность операций для любого входа, принадлежащего классу (этот принцип может применяться не только при рассмотрении той или иной сортировки). Число таких классов может оказаться конечным, даже если само множество входов размера п бесконечно. Если это не противоречит другим предположениям, то такие классы можно рассматривать как элементарные события, приписывая каждому из них некоторую вероятность.
На выполнение любой сортировки с помощью сравнений сами значения элементов х1,х2, ...,хп не оказывают никакого влияния, важен лишь их относительный порядок. Поэтому в один класс естественно объединять все массивы х1,х2,...,хп, имеющие один и тот же порядок элементов по отношению друг к другу. Такой класс может быть представлен перестановкой чисел 1, 2, ...,п с соответствующим порядком элементов (перестановкой длины п). В дальнейшем для любого neN* мы будем рассматривать функцию i/>„, аргументами которой являются любые попарно различные числа х1,х2,...,хп, а значением — перестановка а = (а1,а2, . .., ап) чисел 1, 2, ...,п, отражающая относительный порядок чисел х1,х2, ...,хп. Например,
1/>3 (-34, -10,17) = (2,1, 3). (6.1)
Множество всех перестановок чисел 1,2,..., п будет обозначаться через П„, так же будет обозначаться и вероятностное пространство,
получаемое приписыванием вероятности — каждой из этих перестановок.
Рассмотрим некоторые события в вероятностном пространстве Пп;
вероятность каждого из них, очевидно, будет равна —, где М—число перестановок, составляющих событие. Эту вероятность мы будем обозначать через Pп(-).
Пример 6.1. Начнем с события Bvn, 1^v^n, состоящего в том, что v-й элемент av перестановки (а1,а2, ...,ап) равен v. Перестановку (а1,а2,...,ап)&ип можно рассматривать как отображение множества {1,2, ...,п} на себя, при котором 1 переходит в а1, 2 переходит в а2 и т.д., и событие Bvn состоит тогда в том, что v является неподвижной точкой перестановки. Множество, состоящее из перестановок (а1,а2,..., ап) таких, что av=v, содержит (п-1)! элементов, от-
nv (п-1)! 1 сюда P (В„) = :— = - при всех рассматриваемых v.
В зависимости от выбранной перестановки число неподвижных точек может быть любым целым из диапазона от 0 до п. Рассмотрим
48