может служить использование вектора специальных признаков для
определения принадлежности элементов множества тому или иному
подмножеству его разбиения, отношения
D
“координата элемента в
записи множества
B
соответствует координате ассоциированного с
ним элемента в записи множества
С
”.
Выполним обоснование и оценку эффективности использования
предиката на примере определения принадлежности элемента не-
которому подмножеству разбиения множества. Имеется разбиение
множества
X
=
{
x
i
/i
= 1
, n
}
на
m
непересекающихся подмно-
жеств
Y
=
{
Y
1
, Y
2
, . . . , Y m
}
,
Y j
⊆
X
. Напомним, что для всех
j, r
∈
J
= 1
, m
|
Y j
|
,
|
Y r
| ≥
1
, Y j
∩
Y r
=
∅
и
∪
j
∈
J
Y j
=
X.
В том случае, когда множество
Y
задано перечислением, опре-
деление подмножества, которому принадлежит некоторый элемент
x
i
множества
X
, может потребовать в худшем случае
n
операций его
сравнения с
x
t
∈
Y j
для всех
j
∈
J
. Таким образом, асимптотиче-
ская сложность выполнения этой операции в худшем равна
О
(
n
)
. Из
свойств разбиения множества следует, что каждый элемент множе-
ства может принадлежать только одному подмножеству и подмноже-
ство может включать более одной вершины. Следовательно, разбиение
Y
множества
X
— это сюръективное отношение из
X
в
Y
. Отсю-
да принадлежность элементов
x
i
подмножествам разбиения
Y
может
быть задана образом
Р
X
множества
X
относительно соответствую-
щего этому отношению предиката
Р
(
X, Y
)
:
Р
X
=
{
Р
x
i
/x
i
∈
X
}
,
Р
x
i
=
{
Y j
∈
Y
:
Р
x
i
(
Y j
) =
“и”
}
,
где
Y j
⊆
X.
Для разбиения
Y
=
{
Y
1
, Y
2
, Y
3
}
, где
Y
1 =
{
x
1
, x
3
, x
5
}
,
Y
2 =
=
{
x
4
, x
6
}
,
Y
3 =
{
x
2
}
множества
X
=
{
x
1
, x
2
, x
3
, x
4
, x
5
, x
6
}
образ
этого множества будет
Р
X
=
{
Y
1
, Y
3
, Y
1
, Y
2
, Y
1
, Y
2
}
.
Экономнее задать сюръективное отношение из множества
X
в мно-
жество индексов подмножеств разбиения
Y
. Тогда получим множество
признаков — номеров подмножеств разбиения
B
=
{
b
i
/i
= 1
, n
}
,
где
b
i
=
j,
если
x
i
∈
Y j.
Если множество
Р
X
или
B
представлено вектором, то вычисли-
тельная сложность операции определения подмножества, которому
принадлежит элемент
x
i
, равна
О
(1)
.
Данный способ был использован в алгоритме Краскала [3] и в даль-
нейшем для построения процедур абстрактного типа данных — “мно-
жество” [4]. Применение этого способа в алгоритмах, выполняющих
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 59
