- •Глава 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
§ 8. Функция затрат рандомизированного алгоритма
61
которых не превышает n - 1, при этом не исключается равенство нулю одной из длин. С каждой из двух полосок разрезальщик проделывает ту же операцию, получая вознаграждение в соответствии с тем же принципом оплаты. Каково математическое ожидание размера вознаграждения, получаемого разрезальщиком за всю работу? Здесь при фиксированном n множество всех возможных сценариев (будем называть их n-сценариями) — это фактически множество
3
3
3
3
3
0
0
0
0
1
0
1
0
Рис. 9. Сценарии разрезания полоски из трех клеток (3-сценарии).
некоторых двоичных деревьев; на рис. 9 показано одно из возможных представлений множества всех 3-сценариев. В каждой вершине дерева записывается число клеток в полоске. При произвольном n ^ О понятие п-сценария определяется рекурсивно: О-сценарий и 1-сце-нарий—это одна вершина, которой приписано число 0 или соответственно 1; пусть п > 1,
тогда любой n-сценарий s получается выбо- i - 1 / \ n - i
s'
с"
Рис. 10. Структура п-сценария.
ром некоторого числа i, 1 ^ i ^ п, некоторого (i - 1)-сценария s' и некоторого (п - О-сцена-рия s": из корня п исходят ребра к вершинам i-1 и n-i, к которым подклеиваются корни
сценариев s' и s" (рис. 10). Каждому п-сцена-
рию s естественным образом приписывается
вероятность P„(s) (здесь индекс п указывает
на то, что вероятность соотнесена с некоторым n-сценарием): если
п = 0 или п = 1, то сценарии имеют вероятность 1, а при п > 1
Pn(s) = -Pi_1(s/)P„-i(s/0-
(8.1)
Например, третий из 3-сценариев, изображенных на рис. 9, имеет вероятность ^, каждый из остальных—вероятность -т.
Формула (8.1) отражает идею алгоритма, а именно что после определения i выбор (i - 1)-сценария s' и выбор (п - О-сценария s" независимы друг от друга. Эта формула превращает множество всех п-сце-нариев при фиксированном п в вероятностное пространство S„. Поль-
62
Глава 2. Сложность в среднем
зуясь индукцией по п, проверим, например, что ^ Pn(s) = l: при п = 0 и п = 1 это очевидно, при п > 1 имеем
seS„ i
=
l s'eS-j
s"eS
■i-1
*n-i
Yj((Yj
Pi-^s'A
J] Pn-its"A
i
= l s'eSj-j s"<ESn-i
i=l
Плата за разрезание полоски длины п на отдельные клетки полностью определяется использованным n-сценарием, это задает случайную величину Хп на Sn, и нас интересует математическое ожидание этой величины. Для сценария s, представленного на рис. 10, мы назовем s' и s" левым и правым подсценариями. При п > 1 определим на Sn дополнительно к jn еще две случайные величины %'п и %'^, положив ^(s) = Xi-i(.s') и x'nte) = Xn-i(s"\ где s' и s" суть левый и правый под сценарии сценария s. Имеем при п > 1
jn(s) = n-l + ^(s)+^'(s). Пусть п > 1. Введем разложение
sn=s^ + s;; + ...+s;;, (8.2)
где S^—это событие «левый подсценарий данного n-сценария является (i - 1)-сценарием (и соответственно правый подсценарий является (n-0-сценарием)», i = l,2,...,n. Очевидно,
Pn(S1n) = Pn(S2n) = ... = Pn(Snn) = ±,
поэтому по формуле полного математического ожидания получаем
Л/1 ^_| ««' П'п
1=1
п
1 + ^ ^ (E(^IS^) + Edr^'ISi,)) =
-1 + -У(Eу/-1 + Eгп-Л
i=i
п
1 + - У Eгг-1 = п - 1 + - У Erfc.
=п-1+-п
= П
П
1=1
п п-1
= п-1 + -У Eг,1 = п 2
i=l fc=o
i=i