- •Глава 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
§ 15. Оптимальные алгоритмы
109
Добавим, что никакая сортировка не может иметь сложность T{n) по числу сравнений, допускающую оценку an log2 n + o(n log n), a < 1 (в частности, оценку an log2 n + O{n)),—это следует из того, что для всех достаточно больших n выполнено T{n)>n log2 n - 2n.
Пример 14.3. Обратимся к задаче поиска места элемента в упорядоченном массиве длины n.
Предложение 14.4. Функция f(n) = [log2(n + 1)1 является нижней границей сложности алгоритмов поиска места элемента в упорядоченном массиве длины n c помощью сравнений.
Доказательство. Любой алгоритм поиска места элемента в упо рядоченном массиве фиксированной длины n может быть изображен бинарным деревом. Число листьев такого дерева есть n + 1. Далее рассуждаем так же, как при доказательстве предложения 14.2. □
Пример 14.4. Рассмотрим задачу вычисления an с помощью умножений (пример 4.2). Будем считать n размером входа. Затраты будем измерять количеством умножений.
Предложение 14.5. Функция f(n) = [log2 n] является нижней границей сложности алгоритмов вычисления an с помощью умножений.
Доказательство. На каждом этапе алгоритма мы имеем вычисленный набор степеней
am\am\...,amk\ (14.1)
при этом на начальном этапе набор состоит из одного элемента a1. Выполнив одно умножение, мы, очевидно, не можем увеличить мак симальный показатель m = max{m1,m2, ...,mk} более чем вдвое. По этому если определить на наборах вида (14.1) функцию L, равную log2 n - log2 m, то в результате одного шага (одного умножения) эта функция не может уменьшиться больше чем на 1. В то же время зна чение этой функции на исходном наборе равно log2 n, а на итоговом наборе она заведомо неположительна. □
§ 15. Оптимальные алгоритмы
Нижняя граница сложности класса алгоритмов определяется не единственным образом. Например, f(n) = 0 всегда является нижней границей, равно как и любая отрицательная функция. Чем больше найденная нижняя граница, тем она нетривиальнее и ценнее. Сигналом о том, что мы не сможем построить нижнюю границу большую, чем
ПО Глава 4. Нижняя граница сложности. Оптимальные алгоритмы
уже имеющаяся у нас нижняя граница f(n), может служить, например, наличие A е .s4, для которого TA(n) = f(n). С такой ситуацией мы сталкиваемся в предыдущем параграфе в примерах 14.1 и 14.3. Известный нам алгоритм поиска наименьшего элемента и алгоритм бинарного поиска места элемента в упорядоченном массиве имеет каждый сложность, совпадающую с найденной нижней границей. Эти алгоритмы являются оптимальными в смысле следующего определения.
Определение 15.1. Пусть .s4 — класс алгоритмов решения некоторой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть n—обозначение размера входа. Алгоритм Aе .s4 называется оптимальным в j4, если TA(n) является нижней границей сложности алгоритмов из j4.
Пример 15.1. При получении нижней границы сложности и доказательстве оптимальности иногда бывает полезным привлечение функций на наборах тех величин, которые возникают в процессе выполнения алгоритма, например, на наборах значений переменных, используемых алгоритмом.
Предложение 15.1. Функция f(n) = Г2 n1 - 2 является нижней границей сложности алгоритмов одновременного выбора наибольшего и наименьшего элементов массива длины n c помощью сравнений.
Доказательство. Каждый этап выполнения произвольного алгоритма V, основанного на сравнениях и предназначенного для поиска наибольшего и наименьшего элементов массива, может быть охарактеризован четверкой ( A, B, C, D) подмножеств множества исходных элементов {xг, x2, ■ ■ ■, xn}, где
A состоит из всех тех элементов, которые вообще не сравнивались;
B состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались большими;
C состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались меньшими;
D состоит из всех тех элементов, которые участвовали в некоторых сравнениях, иногда оказываясь большими, а иногда — меньшими.
Пусть a, b,c,d — количества элементов множеств A, B, C, D соответственно. Исходная ситуация характеризуется равенствами a = n, b = = c = d = 0. После завершения алгоритма должны выполняться равен-