- •Глава 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. Добавление нулей
Ряд алгоритмов целочисленной арифметики и теории матриц оказывается достаточным (без нанесения сколь-либо существенного ущерба идее алгоритма и его качеству) описать для случая, когда размер
!См., например, [4].
§ 27. Добавление нулей 173
входа есть число вида 2к. При использовании стратегии «разделяй и властвуй» это облегчает и описание алгоритма, и анализ его сложности. С теоретической точки зрения для задачи умножения двух целых чисел а и Ъ мы можем предполагать, что битовая длина каждого из данных чисел равна 2к, где
fc = max{[log2 А(а)1, flog2A(b)l}, (27.1)
так как всегда возможно добавить спереди любого из данных чисел некоторое количество нулей. Если речь идет об умножении квадратных матриц А и В произвольного порядка п, то мы можем добавить к матрицам несколько нулевых строк и столбцов так, чтобы сделать их порядки равными 2Г1о&п1:
А ОЛ (В ОЛ (АВ О
A0 B0 AB0 00 00 00
О 00 00 О (27.2)
(нулями обозначены нулевые блоки соответствующего размера). Несмотря на переход от начальных данных к более громоздким, некоторые из алгоритмов, основанных на стратегии «разделяй и властвуй» и использующих этот переход, имеют существенно меньшую сложность, чем наивные алгоритмы.
Предложение 27.1. Пусть вещественная функция f натурального аргумента такова, что /(п) =/(2г1о&"1) для всех neN+ и
/(2fc)^
u, если k=0,
wf(2k-1) +ϕ(2k), если k >0,
при
fceN,
где
u,w
—
вещественные
числа,
причем
и^О,
w^l,
a ip —
неотрицательная
функция,
определенная
для
всех
п
е
N+.
Тогда
при
всех
п
е
N+
выполняется
неравенство
(и,
если
п
= 1,
/Тп-П Пое.п (27.3)
^/gij^
+^(2nog2ni))
еслип>1_
|"log2|"|]]=riog2nl-l. (27.4)
В самом деле, если 2к-г < п s= 2к, к > 1, то 2к-2 < Г|1 s= 2к-х, т. е. если [log2nl=fc, то riogJ|ll =к-1. Для случая n = 2rlo&nl неравенство (27.3) выполнено по условию, для остальных случаев используем равенства /(n) = /(2rlo&nl), /ГГ-11 = /(г1"10^1""/2"1"1) = /(2rlog2п_|-1). □
174 Глава 6. Рекуррентные соотношения и сложность алгоритмов
Теорема 27.1. Пусть вещественная функция f натурального аргумента такова, что /(п) =/(2г1о&"1) для всех neN+ и
Я2Ц
и, если к = 0,
wf(2fc-1)+c(2fc)d, еслик>0,
при fc е N, где и,d ^ О, о О, w ^ 1. Тогда при рассмотрении f как функции, определенной для всех п е N+ выполняются оценки
(o(ndlogn), если d = log2w,
f(n) = \o{nd), если d>log2w,
[о(п1о&№), если d<log2 мл
Доказательство следует из предложения 27.1 и теоремы 26.1. □
Подобно тому, как доказательство теоремы 26.1 было преобразовано в доказательство теоремы 26.2, из приведенного выше доказательства мы можем получить доказательство следующей теоремы
Теорема 27.2. Пусть вещественная функция f натурального аргумента такова, что /(п) =/(2г1о&"1) для всех neN+ и
/<2Ц
и, если к = 0,
wf(2fc-1)+c(2fc)d, еслик>0,
где и, d ^ 0, о 0, w^ 1. Тогда для функции f{n), при рассмотрении ее как функции, определенной для всех п е N+ выполнено
fn(ndlogn), если d=log2w,
f{n) = I П(п1о& w), если d > log2 w,
[n(nd), если d<log2w.
Перейдем к примерам.
Пример 27.1 (умножение Карацубы). Пусть а и Ъ — целые положительные числа битовой длины т = 2к. Положив Z = 2fc-1, можем записать
a = e2l+f, b = g2l+h,
где e,f,g,h — целые числа битовой длины Z. А.А.Карацубе принадлежит замечательное наблюдение, позволяющее вычислить произведение ab, выполнив всего три умножения чисел половинной длины, несколько сдвигов (домножений на 2т и 21) и несколько аддитивных операций над числами битовой длины s= 2т:
аЪ = eg221 + ((е + /) (g + К) - eg - fh)2l + fh, (27.5)