Рис. 1. Классификация способов снижения вычислительной сложности алго-
ритмов
для их реализации
. В этом способе целесообразно выделить две груп-
пы:
— заменяемые и заменяющие выражения состоят из одних и тех
же подмножеств;
— в заменяемые и заменяющие выражения могут входить и разные
подмножества, на отношения между которыми наложены дополни-
тельные условия.
К первой группе относятся, например:
— замена выражения вида
X
⊆
Y
•
Z
или
X
⊂
Y
•
Z
, где
Z
⊆
⊆
X
(
Z
⊂
X
)
, на конструкцию вида
{
X
\
Z
} ⊆
Y
или
{
X
\
Z
} ⊂
Y
;
— использование для определения состава некоторого подмноже-
ства вместо выражения
X
\{
Y
∪
Z
}
выражения
X
\
Y
\
Z
, где
X
,
Y
,
Z
⊂
U
(в частном случае
Y, Z
⊂
X
).
Эффективность преобразования первой группы рассмотрим на
примере операции строгого включения. В эквивалентности выра-
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 55
