Временная сложность 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] Недетерминированные алгоритмы не являются вероятностными; они являются алгоритмами, которые могут находиться одновременно во многих состояниях.