- •Глава 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. Сложность в среднем
Пример 6.2. Исследуем сложности в среднем по числу сравнений и перемещений сортировки простыми вставками, которую, как и прежде, мы будем рассматривать в двух вариантах \г и 12 (см. пример 1.4). Вначале займемся первым вариантом \г этой сортировки, полагая затраты равными числу сравнений. Входные массивы считаем перестановками чисел 1,2,..., п. Для исследования сложности по числу сравнений введем случайные величины Е}п, С •••> Ъп-г, определенные так, что значение Е,1п для
а=(а1,а2,...,ап)∈П„
равно затратам на i-м шаге нашей сортировки, применяемой к а. Ясно, что интересующее нас математическое ожидание есть Е(^ + ^ + ... +CJJ-1), и
7}i(n) = E^ + E?2 + ... + Eq-1. (6.4)
Найдем ?п, l^i<n. Рассматривая события H*-l+1, fc = 0, l,...,i, образующие разложение пространства П„, и применяя формулу (6.3) полного математического ожидания, мы имеем согласно предложению 6.1(iii)
ЕГ=ДтУЕ(Г|Я^+1). (6.5)
fc=0
Если перестановка а = {аъа2,...,ап) принадлежит событию Н^+, то в этой перестановке перед элементом ai+1 имеется ровно к элементов, меньших его, и, очевидно,
._fi-fc + l, если/с>0, n~i, если/с = 0.
Мы видим, что при выполнении события H^I+1 значение Е,1п определено однозначно (напомним, что значение E,ln, i = 1, 2,..., п - 1, равно числу сравнений на i-м шаге, а перед выполнением i-го шага элементы a1,a2,...,ai уже упорядочены по возрастанию). Поэтому
. м+1 fi-fc + 1, если/с>0, " "' i, если fc = 0.
В соответствии с (6.5)
fc=i
§ 6. Сортировка и конечные вероятностные пространства 51
Используя (6.4), получаем выражение
п-1 +
п-1
fi
1
2 i + l
i = l
для искомой сложности в среднем. С помощью известной из математического анализа формулы (ее вывод имеется в приложении B)
п
Y, у = Inn+ 0(1)
i=l
сложность T^in) можно записать в виде
Т}1(п)=("
+
4)("-1)-1пп
+ 0(1) (6.6)
[К 4 и, проще, в виде
Г; (п) = ^+0(п). (6.7)
п_2 4
Таким образом, сложность в среднем по числу сравнений первого варианта сортировки простыми вставками, как и сложность в худшем случае, есть величина порядка п2, но при больших п первая сложность примерно вдвое меньше второй. Формула (6.6) показывает, что, вообще говоря, вопреки бытовым представлениям сложность в среднем не есть среднее арифметическое затрат в худшем и в лучшем случае: такое среднее арифметическое для рассматриваемой сортировки является рациональной функцией от п и не может описываться этой формулой, содержащей логарифм.
Если рассмотреть вместо случайных величин Е}п, £2,..., Е^х случайные величины г\\, г;2,..., rfn_1, соответствующим образом отражающие затраты исследуемой сортировки по числу перемещений, то, очевидно, будем иметь
^ *S r,j, *S ?j, + 1,
i = 1, 2,..., n - 1. Поэтому сложность в среднем по числу перемещений
п2 тоже есть — +0(п). Нетрудно показать, что и сложности в среднем
по числу сравнений и числу перемещений второго варианта сортировки простыми вставками равны — + 0{п). Сложность в среднем по суммарному числу сравнений и перемещений и для первого, и для второго варианта есть ^+0(п), поскольку для любых случайных величин Е,,г), определенных на каком-либо вероятностном пространстве, выполняется
Е(? + т)) = Е? + Ет). (6.8)
52