- •Глава 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
§ 27. Добавление нулей 175
тогда как обычное раскрытие скобок в (e2l + f)(g2l + К) требует выполнения четырех таких умножения:
ab = eg22l + (eh + fg)2l+fh. (27.6)
Мы видим, что формула (27.5) использует произведения eg, fh, (e + /)(g + h), а формула (27.6)—произведения eg,eh,fg,fh.
Небольшая проблема, которая выше была замаскирована словами «половинная длина», состоит в том, что битовая длина любого из чисел e + f, g + h, входящей в произведение (е+ /)(# +ft), может оказаться равной Z +1, а не Z. Но если
e + f = ex2l+fx, g + h = g12l + hi,
где e1,g1 — однобитовые числа (0 или 1), то
(е + f)ig + K)= elgl221 + (exhx + g1/1)2l + fxhx. (27.7)
Произведение Л 7^ вычисляется рекурсивным обращением к алгоритму, произведения e1g1,e1h1,g1f1, как и все сложения и сдвиги, требуют 0(1) операций.
Равенство (27.5) и предположение, что т = 2к, приводят к рекурсивному алгоритму Карацубы умножения целых положительных чисел (будем обозначать этот алгоритм буквами KM: первая из этих букв — начальная в фамилии автора алгоритма, вторая — в английском слове multiplication —умножение). Предположение т = 2к приводит к следующему соотношению для битовой сложности умножения Карацубы:
( 1, если т = 1,
ГтЛ (27.8)
ЗГКМ1 у I +ст, еслит>1,
где с — некоторая положительная константа.
Умножение Карацубы при произвольном входе a, b е N+ размера т = шах{А(а), А(Ь)} предполагает, что сначала мы находим к = = [log2ml, затем добавляем спереди каждого из а,Ъ некоторое количество нулей так, чтобы битовая длина каждого из сомножителей стала равной 2к, а после этого используем рекурсивный алгоритм, основанный на (27.5).
Мы можем применить теорему 27.1 (w = 3, d = 1), так как при произвольном meN+ выполняется Гкм(т) = Гкм(2Г1о&т1). Получаем
Гкм(т) = 0(т1о&3), (27.9)
при этом log2 3 = 1,58...
176 Глава 6. Рекуррентные соотношения и сложность алгоритмов
Для m > 1 мы имеем
TKM(m)>G(m), (27.10)
где функция G натурального аргумента такова, что G(m) = G(2n°^m]) для всех m е N+ и
G(2k) =
1, еслиk=0,
3G(2k-1), если k >0,
откуда Tкм(m) = П(m1о&3) по предложению 27.2. Вместе с (27.9) это дает
Tкм(m) = в(m1о&3). (27.11)
При использовании m, равного максимальной из битовых длин двух данных чисел a, beN+ в качестве размера входа битовая сложность умножения Карацубы допускает оценку
Tкм(m) = в(m1о&3),
при том, что Tмм = 6(m2) — оценка битовой сложности наивного умноженияг.
Стратегия добавления нулей особенно характерна для исследований, в которых главной целью служит преодоление некоторого слож-ностного барьера; последнее было и остается важным стимулом развития теории сложности.
Пример 27.2. Алгоритм Штрассена умножения двух квадратных числовых матриц A и B порядка n, являющегося степенью двойки, основан на том, что если n = 2l и
A = [A11 A 12Л =(BU B 12Л
A 21 A2> B B 21 B22>
где все Aij,Bij — квадратные матрицы порядка l, то матрицу
C=AB= CC
можно получить, выполнив семь умножений квадратных матриц порядка l (при том, что потребовалось бы восемь таких умножений при
1 История создания алгоритма Карацубы и публикации о нем в 1962 г. сообщения [15] увлекательно рассказана в статье [17] самого А. А. Карацубы; особенно богат яркими историческими деталями раздел 6 этой статьи.