Классификация способов снижения вычислительной сложно-
сти алгоритмов, использующих свойства множеств, предикатов и
операций над ними.
Под
оптимизирующими преобразованиями
бу-
дем понимать совокупность эвристических приемов модификации ал-
горитмов, которые позволяют в определенных случаях снижать их
вычислительную сложность.
Оптимизационный эффект применения способов снижения вычи-
слительной сложности калгоритму достигается удалением лишних
вычислений посредством замены части алгоритма на более эффектив-
ную, т.е. имеющую меньшую вычислительную сложность. Эта транс-
формация должна быть
корректной
, т.е. сохранять эквивалентность
исходного и полученного алгоритмов.
Исходный и преобразованный алгоритмы
эквивалентны
, если на
всех допустимых наборах входных данных задачи дают одинаковые
результаты.
Корректность
изменений подразумевает эквивалентность
заменяемого и заменяющего фрагментов и удовлетворение контекст-
ных условий на требуемые свойства объектов алгоритма и/или связи
заменяемого фрагмента с остальной частью алгоритма. Такими усло-
виями являются, например, проверки наличия в алгоритме операторов
и/или объектов, позволяющих использовать заменяющий фрагмент.
В [1] отмечено, что вычислительная сложность алгоритма зави-
сит от многих факторов. В настоящей статье рассматриваются только
способы снижения вычислительной сложности алгоритмов, использу-
ющие свойства множеств, предикатов и операций над ними. Класси-
фикация этих способов приведена на рис. 1.
Оптимизирующие преобразования, использующие свойства
множеств и операций над ними.
Первый способ этой группы пре-
образований
заключается в реализации операции удаления элемента
множества посредством его замены другим, например последним.
Способ базируется на основном свойстве множества, т.е. применение
его возможно, если элементы множества не упорядочены по какому-
либо правилу и оно не участвует в дальнейших преобразованиях в
первоначальном виде. Отметим, что в случае необходимости множе-
ство можно предварительно копировать. Информацию о возможности
реализации способа нетрудно получить из описания алгоритма в тер-
минах операций над графами и множествами.
Оценим эффективность применения способа. Пусть из множества
A
необходимо выбирать и удалять некоторый элемент. Оценка “в худ-
шем” числа операций для удаления сдвигом равна
n
−
1
. Удаление
замещением будет выполнено за одну операцию.
Второй способ
—
это замена выражений алгебры подмножеств
логически эквивалентными и требующими меньшего числа операций
54 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
