Способы снижения вычислительной сложности алгоритмов …
7
(элементов)
2
2
\
i
X X X
=
, если
⎪
X
i
⎪
ограничена константой. Тогда
вычислительная сложность определения
X
2
будет равна
O
(
n
). Третье
и четвертое преобразования можно формализовать.
Заключение.
Представленные результаты исследований показа-
ли возможность и эффективность использования оптимизирующих
преобразований, основанных на пошаговом принципе формирования
решения. Асимптотическая оценка вычислительной сложности алго-
ритмов, основанных на методах последовательного формирования и
итерационного улучшения, снижается с
O
(
n
2
) до
O
(
n
), что весьма су-
щественно для алгоритмов решения задач структурного синтеза с
большой размерностью входа.
ЛИТЕРАТУРА
[1] Овчинников В.А. Математические модели объектов задач структурного
синтеза.
Наука и образование
, 2009, № 3. URL:
doc/115712.html.
[2] Овчинников В.А.
Алгоритмизация комбинаторно-оптимизационных задач
при проектировании ЭВМ и систем
. Москва, Изд-во МГТУ им. Н.Э. Баумана,
2001.
[3] Касьянов В.Н., Евстигнеев В.А.
Графы в программировании: обработка,
визуализация и применение
. Санкт-Петербург, БХВ-Петербург, 2003.
[4] Овчинников В.А., Иванова Г.С. Информационно-логическая модель ал-
горитма.
Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение
, 2005,
№ 2 (59), c. 109–121.
[5] Иванова Г.С.
Методология и средства разработки алгоритмов решения
задач анализа и синтеза структур программного обеспечения и
устройств вычислительной техники
. Дис. ... д-ра техн. наук. Москва,
2007.
Статья поступила в редакцию 28.06.2013
Ссылку на эту статью просим оформлять следующим образом:
Овчинников В.А. Способы снижения вычислительной сложности алгоритмов,
вытекающие из принципа формирования решений.
Инженерный журнал: наука и
инновации,
2013, вып. 11. URL:
Овчинников Владимир Анатольевич
родился в 1939 г., окончил МВТУ
им. Н.Э. Баумана в 1961 г. Д-р техн. наук, профессор кафедры «Компьютерные
системы и сети» МГТУ им. Н.Э. Баумана, академик Международной академии
информатизации. Автор свыше 120 научных работ в области вычислительной тех-
ники. Специализируется в области автоматизации проектирования компьютерных
систем. е-mail:
