Автоматизация анализа вычислительной и емкостной сложности алгоритмов…
7
емкостных сложностей структур данных, представляющих графовые
модели
G
i
:
1
( ).
r
A
i
i
L L S
Поскольку вычислительная и временная сложности по опре-
делению пропорциональны, расчетные соотношения пп. 4–7 позво-
ляют также оценить время выполнения программы, реализующей
разрабатываемый алгоритм. В качестве исходных данных для такого
расчета следует вместо функциональной вычислительной сложности
Q
d
(
S
i
) (см. п. 4) использовать оценки времени выполнения операций
над структурой данных, реализующей
i
-й граф —
T
d
(S
i
).
Полученные по перечисленным выше расчетным соотношениям
значения вычислительной, временной и емкостной сложности дол-
жны проверятся разработчиком алгоритмов на допустимость. В том
случае, если время или объем используемой памяти не соответствует
требованиям, разработчик должен оптимизировать разрабатываемый
алгоритм или использовать другой метод решения задачи.
Заключение.
Предложенные в настоящей работе расчетные
соотношения и методика оценки вычислительной, временной и ем-
костной сложности алгоритмов решения задач структурного анализа
и синтеза позволяют автоматизировать трудоемкий процесс анализа
разрабатываемых алгоритмов и получать более точные оценки
наиболее существенных временных и емкостных характеристик этих
алгоритмов. В результате сокращается время разработки программ
решения задач структурного анализа и синтеза и появляется возмож-
ность улучшения их качества.
ЛИТЕРАТУРА
[1] Кормен Т., Лейзерсон Ч., Риверст Р., Штайн К.
Алгоритмы: построение и
анализ
. Москва, Вильямс, 2005, 1296 с.
[2] Кнут Д.Э.
Искусство программирования
. Москва, Наука, 2006, 437 с.
[3] Vitter J., Flajolet Ph. Average-Case Analyse of Algorithms and Data Structure.
Handbook of Handbook of theoretical computer science: algorithms and
complexity
, 1991, vol. A, pp. 431–524.
[4] Овчинников В.А., Иванова Г.С. Информационно-логическая модель
алгоритма.
Вестник МГТУ им. Н.Э. Баумана
.
Сер. Приборостроение
, 2005,
№ 2(59), с. 109–121.
[5] Иванова Г.С. Формальная постановка задачи структуризации алгоритмов.
Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение
, 2005, № 3 (60),
с. 64–73.
[6] Вирт Н.
Алгоритмы и структуры данных. Новая версия для Оберона
.
Москва, ДМК Пресс, 2010, 406 с.
[7] Иванова Г.С. Математические модели структур данных.
Информационные
технологии
, 2006, № 9, с. 44–52.
