Временная сложность T(N)

Примем для простоты, что все операции (присваивание, добавление 1 при счёте, выборка из множества символа или элемента либо их занесение в множество, конкатенация элемента и символа, вывод элемента множества на печать либо экран) выполняются за единицу времени. Тогда можно считать, что основное время тратится на формирование подмножеств QL и Q’L, причём на Q’L примерно вполовину меньше. Поэтому

T(N)==2^N-2+2^N-1-1@

@1.5*2^N-1 = O(2^N).

Итак, оценкой временной сложности является T(N) = O(2^N).

Ёмкостная сложность Е(N)

В худшем случае, если в памяти хранятся все подмножества QL и Q’L (объёмом памяти, занимаемым простыми переменными и параметрами цикла, а также исходным множеством М, пренебрегаем), оценка ёмкостной сложности определяется величиной Е(N) = O(2^N). Если же хранить в памяти только текущее подмножество Q’L, а по нему формировать элементы подмножества QL и тут же их выводить, затем формировать новое подмножество Q’L, при этом исключая особые элементы в подмножестве QL, то оценкой ёмкостной сложности будет Е(N) = O(С^R_N-1), где R=](N-1)/2[ - целая часть дроби (N-1)/2. Действительно, максимальное количество элементов содержит подмножество, длина элементов которого равна округлённо половине числа символов без 1 в множестве М.

Итак, оценкой ёмкостной сложности является T(N) = O(С^R_N-1).

Заключение

При разработке эффективных алгоритмов необходимо использовать как структуры высокого уровня (списки, очереди, стеки), так и мощную технику рекурсии и динамического программирования. Важными являются приёмы общего вида “разделяй и властвуй” и “балансировка”. Существуют и другие методы повышения эффективности алгоритмов [2, 10, 13]. Разработчик алгоритмов должен изучить задачу с разных точек зрения, пока не убедится, что получил алгоритм, наиболее подходящий для его целей.

Полезными являются вопросы к основным этапам полного построения алгоритма, сформулированные в подразд. 4.4.1.

Для анализа построенного алгоритма важно уметь применять формулы, соотношения и асимптотики комбинаторики.

Контрольные вопросы. Упражнения

1. Каковы достоинства рекурсии? Каковы её недостатки? Когда целесообразно её применение?

2. Чем отличается рекурсивное построение алгоритма от итера-ционного? В каких случаях целесообразно применение итерационных алгоритмов?

3. Постройте рекурсивный и нерекурсивный алгоритмы для пере-мещений дисков на свободный стержень в задаче “Ханойские башни” (см. подразд. 1.3.2).

4. Составьте списки констант, переменных, массивов и процедур с расшифровкой их функционального назначения для задачи подразд. 4.4.2. Докажите, что если S0 – количество особых элементов, то S1=S-S0=.

[1] Под ²состоянием² понимаются адрес текущей команды и значения всех переменных.

[2] Недетерминированные алгоритмы не являются вероятностными; они являются алгоритмами, которые могут находиться одновременно во многих состояниях.

Дата добавления: 2014-01-14