Емкостная сложность алгоритма

Емкостная сложность характеризует объем памяти, который необходим для реализации алгоритма. В общем случае объем, который для этого необходим, включает в себя память, требуемую для программы, исходных данных, а также промежуточных и конечных результатов.

При разработке алгоритма оцениваются последние три составляющие. Единица измерения может быть как общепринятая, так и некоторая условная. Оценка емкостной сложности – простая задача, хотя, в ряде случаев, может быть достаточно трудоемкой. При использовании сложных иерархических структур данных задача выбора размеров указателей и прочих компонентов может быть достаточно сложной.

Вычислительная и ёмкостная сложность скоррелированы: как правило, снижение вычислительной сложности достигается за счёт увеличения ёмкостной и наоборот. В качестве обобщенной характеристики сложности алгоритма было предложено использовать так называемый коэффициент сложности , где N – суммарное количество эталонных (или доминирующих) операций, V – общий объем памяти.

Основные этапы построения алгоритма. Сущ-ть алг. решения задачи на графах.

Разработка алгоритма – итерационный процесс, не всегда удается выбрать метод решения задачи до разработки алгоритма. Нередко предварительно можно лишь определить круг возможных методов, а сам метод приходится выбирать в ходе разработки алгоритма. Поэтому рассмотрим этапы и порядок их выполнения (их следует воспринимать как общее руководство).