В.А. Овчинников
6
Рис. 2.
Текущий шаг работы алгоритма, при выполнении которого в множе-
ство
X
l
включается вершина
x
t
Тогда множество
п
к к \ , к к
.
t
t
X X x X X X
=
= ∪
Так как
(
)
п
max
1
t
X
A
< ρ −
и, согласно закону Рента,
(
)
max
к
1
p
l
X
A n
= ρ −
, где
0,5...0,75
p
=
,
вычислительная сложность определения множество
X
к будет от
O
(
n
0,5
) до
O
(
n
0,75
).
Возможность формализации данного способа такая же, как и у
предыдущего.
Способы, выполняющие замену операций на более эффек-
тивные.
Третий способ
базируется на том, что при решении задач
структурного анализа и синтеза обычно рассматриваются фрагменты
графов с непересекающимися подмножествами вершин, а в ряде слу-
чаев и ребер. Очевидно, что при объединении непересекающихся
подмножеств нет необходимости проверять, совпадают ли их элемен-
ты. Таким образом, при
1
2
X X
∩ = ∅
операцию
1
2
X X X
= ∪
следует
заменить на
1 2
X X X
= ⋅
, что позволяет снизить вычислительную
сложность этой операции с
O
(
n
2
) до
O
(
n
) при представлении мно-
жеств векторами и до
O
(1) при представлении списками с указателя-
ми их начала и конца. Следует, однако, помнить, что во втором слу-
чае множество
X
2
не сохраняется.
Применение
четвертого способа
возможно, если при переносе
элементов или подмножеств из одного множества в другое множе-
ства формируются следующим образом:
1
1
2
1
:
,
\ .
i
X X X X X X
= ⋅
=
Если
⎪
X
1
⎪
ограничена величиной
n
, вычислительная сложность опре-
деления множества
X
2
равна
O
(
n
2
). В этом случае множество
X
2
сле-
дует получать как дополнение до него переносимых подмножеств
