Оценка числа операций сравнения, необходимых для проверки
условия по фрагментам 3–6, показывает, что
k
op
3
,
k
op
4
,
k
op
6
> k
op
2
и
k
op
5
=
k
op
2
, где
k
opi
— число сравнений элементов множеств
X, Y, Z
,
необходимых для проверки условия по
i
-й формуле. Таким образом,
фрагменты 1, 3, 4 и 6 являются заменяемыми, а фрагмент 2 или 5 —
заменяющим.
Продолжим анализ. Операция
X
\
Z
эквивалентна
X
∩
Z
, отсюда
получаем следующий набор логически эквивалентных фрагментов:
7)
X
∩
Z
⊆
Y,
8)
{
X
∩
Z
} ∩
Y
=
X
∩
Z,
9)
{
X
∩
Z
} ∪
Y
=
Y,
10)
{
X
∩
Z
}\
Y
=
∅
,
11)
{
X
∩
Z
}∩
Y
=
∅
,
12)
{
X
∩
Z
}∪
Y
=
U.
Все эти фрагменты также являются заменяемыми. Покажем это.
Для определения
X
\
Z
и
X
∩
Z
требуется выполнить
|
X
|×|
Z
|
и
|
X
|×
× |
Z
|
+ (
|
X
| − |
Z
|
)
× |
X
|
=
|
X
|
2
операций сравнения соответственно.
С учетом того, что
Z
⊂
X
, справедливость утверждения очевидна.
В качестве примера преобразований второй группы можно приве-
сти замену выражения
x
i
∈
X
1
на
x
i
/
∈
X
2
и выражения
X
i
⊂
X
1
на
X
i
∩
X
2
=
∅
,
X
i
∩
X
1
=
∅
на
X
i
⊆
X
2
, если
X
2
=
X
\
X
1
,
|
X
1
|
>
|
X
|
2
,
x
i
∈
X
или
X
i
⊂
X
. Очевидно, что при использовании этого преобра-
зования число операций сравнения сокращается в
k
=
|
X
1
|
/
|
X
2
|
раз.
Способ легко формализовать.
Два следующих способа снижения вычислительной сложности
основаны на использовании свойств операций над множествами, за-
данными перечислением.
Третий способ
—
выбор порядка выполнения операции пересечения
более чем двух множеств
. Заданы множества
X, Y, Z
⊂
U
. Обозначим
|
X
|
=
n
,
|
Y
|
=
m
,
|
Z
|
=
k
. Преобразование основано на использо-
вании свойств коммутативности и ассоциативности операции пересе-
чения и предположении, что число сравнений при пересечении более
чем двух множеств можно сократить за счет выбора порядка выполне-
ния операции над парой множеств. Напомним, что упомянутые законы
для трех множеств имеют соответственно вид
X
∩
Y
∩
Z
=
Y
∩
X
∩
Z
=
. . .
и
(
X
∩
Y
)
∩
Z
=
X
∩
(
Y
∩
Z
) = (
X
∩
Z
)
∩
Y.
В табл. 1 приведены результаты анализа трех возможных вариантов
порядка определения пересечения множеств
X, Y, Z
.
Положим для определенности, что
n > m > k
. В общем слу-
чае второй вариант порядка выполнения операции предпочтительнее
первого, если
nm
+
|
X
∩
Y
|
k > mk
+
|
Y
∩
Z
|
n
; третий вариант по-
рядка выполнения операции предпочтительнее первого, если
nm
+
+
|
X
∩
Y
|
k > nk
+
|
X
∩
Z
|
m
.
Рассмотрим некоторые частные случаи. Минимальное число опе-
раций сравнения для первого порядка определения пересечения трех
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 57
