Исключение

Множество представлено битовым вектором

Исключение элемента x из множества A сводится к установке бита с номером, в 0. Вычисления сводятся к выполнению след. операций:

bit = ~ (bit>>k);

j = i/16; k = i % 16;

qx = B[j] & bit;

Отсюда время выполнения этой операции также равно: t = Const.

Множество представлено одномерным массивом

Операция A-x может быть реализована такими операторами:

for (i = 0; i < n; i++) if (x == A[i]) break;

for (k = i; k < n-1; k++) A[i] = A[i+1];

Время выполнения обоих циклов будет равно:

t = c₁n₁+c₂n₂,

где c₁ - время выполнения операции сравнения, c₂ - время выполнения операции присваивания (пересылки), n₁ – к-во итераций первого цикла, n₂ – к-во итераций второго цикла. Пусть c = max(c₁,c₂), тогда, учитывая, что n = n₁+n₂, получаем:

t ≤ Const×n.

Множество представлено упорядоченным массивом

Алгоритм такой же, как и для представления мн-ва неупорядоченным массивом. Для снижения времени можно использовать алгоритм бинарного поиска, однако порядок алгоритма остается таким же:

t ≤ Const×n.

Объединение

Множество представлено битовым вектором

Определение операции объединения: AÈB = { x | xÎA или xÎB }.

Операция сводится к поэлементному выполнению операции дизъюнкции над парами соответствующих битов. Реализовать это можно следующим образом:

for (i = 0; i < m;i++) C[i] = A[i] || B[i];

Здесь символы A,B,C используются как имена множеств и, в то же время, как имена соответствующих массивов-носителей.

Т.к. m и N связаны линейным соотношением (1), то при достаточно больших N будем иметь:

t = Const ∙N.

Множество представлено одномерным массивом

Операция AÈB. Пусть n_A = |A|, n_B = |B|. Данную операцию можно рассматривать как последовательность операций включения: для каждого элемента мн-ва В необходимо выполнить операцию вкючения его в м-во А. Т.к. операция включения требует линейного времени, имеем:

t ≤ Const×n_An_B.

Множество представлено упорядоченным массивом

Можно использовать идею алгоритма слияния, которая используется для сортировки. Тогда упорядоченность массивов, представляющих множества, дает алгоритм с временем:

t = Const (n_A+n_B),

т.е. имеем линейный по времени алгоритм.