- •Глава 4
- •4.1. Комбинаторные вычисления на конечных множествах
- •4.1.2. Асимптотика
- •Говорят, что при Xx0 f(X) растёт медленнее, чем g(X), или что f(X) "есть о-малое" от g(X).
- •Отсюда, в частности, имеем при n
- •4.1.3. Рекуррентные соотношения
- •Последовательность Фибоначчи асимптотически растёт как
- •4.1.4. Производящие функции
- •4.2. Оценки сложности алгоритмов
- •4.3. Методы повышения эффективности алгоритмов
- •4.3.1. Рекурсия
- •4.3.2. Приём “разделяй и властвуй”
- •4.3.3 Принцип балансировки
- •4.3.4. Динамическое программирование
- •4.3.5. Алгоритмы с возвратом
- •Понимание постановки задачи
- •Составление плана решения
- •Взгляд назад
- •Основные этапы полного построения алгоритма
- •Постановка задачи
- •Временная сложность t(n)
- •Ёмкостная сложность е(n)
- •Заключение
- •Контрольные вопросы. Упражнения
Временная сложность t(n)
Примем для простоты, что все операции (присваивание, добавление 1 при счёте, выборка из множества символа или элемента либо их занесение в множество, конкатенация элемента и символа, вывод элемента множества на печать либо экран) выполняются за единицу времени. Тогда можно считать, что основное время тратится на формирование подмножеств QL и Q’L, причём на Q’L примерно вполовину меньше. Поэтому
T(N)==2N-2+2N-1-1
1.5*2N-1 = O(2N).
Итак, оценкой временной сложности является T(N) = O(2N).
Ёмкостная сложность е(n)
В худшем случае, если в памяти хранятся все подмножества QL и Q’L (объёмом памяти, занимаемым простыми переменными и параметрами цикла, а также исходным множеством М, пренебрегаем), оценка ёмкостной сложности определяется величиной Е(N) = O(2N). Если же хранить в памяти только текущее подмножество Q’L, а по нему формировать элементы подмножества QL и тут же их выводить, затем формировать новое подмножество Q’L, при этом исключая особые элементы в подмножестве QL, то оценкой ёмкостной сложности будет Е(N) = O(СRN-1), где R=](N-1)/2[ целая часть дроби (N-1)/2. Действительно, максимальное количество элементов содержит подмножество, длина элементов которого равна округлённо половине числа символов без 1 в множестве М.
Итак, оценкой ёмкостной сложности является T(N) = O(СRN-1).
Заключение
При разработке эффективных алгоритмов необходимо использовать как структуры высокого уровня (списки, очереди, стеки), так и мощную технику рекурсии и динамического программирования. Важными являются приёмы общего вида “разделяй и властвуй” и “балансировка”. Существуют и другие методы повышения эффективности алгоритмов [2, 10, 13]. Разработчик алгоритмов должен изучить задачу с разных точек зрения, пока не убедится, что получил алгоритм, наиболее подходящий для его целей.
Полезными являются вопросы к основным этапам полного построения алгоритма, сформулированные в подразд. 4.4.1.
Для анализа построенного алгоритма важно уметь применять формулы, соотношения и асимптотики комбинаторики.
Контрольные вопросы. Упражнения
1. Каковы достоинства рекурсии? Каковы её недостатки? Когда целесообразно её применение?
2. Чем отличается рекурсивное построение алгоритма от итера-ционного? В каких случаях целесообразно применение итерационных алгоритмов?
3. Постройте рекурсивный и нерекурсивный алгоритмы для пере-мещений дисков на свободный стержень в задаче “Ханойские башни” (см. подразд. 1.3.2).
4. Составьте списки констант, переменных, массивов и процедур с расшифровкой их функционального назначения для задачи подразд. 4.4.2. Докажите, что если S0 – количество особых элементов, то S1=S-S0=.
1 Под состоянием понимаются адрес текущей команды и значения всех переменных.
2 Недетерминированные алгоритмы не являются вероятностными; они являются алгоритмами, которые могут находиться одновременно во многих состояниях.