2015-05-22
322
Множество представлено битовым вектором
AÇB = { x | xÎA и xÎB }.
Реализация этой операции выглядит так:
for (i = 0; i < m; i++) C[i] = A[i] & B[i];
и время выполнения этой операции такое же:
t = Const ∙N.
Множество представлено одномерным массивом
Операция AÈB. Здесь ситуация похожая: для каждого элемента мн-ва А необходимо проверить принадлежность его к мн-ву В. Отсюда:
t ≤ Const×nAnB.
Множество представлено упорядоченным массивом
Для пересечения легко строится алгоритм со временем:
t = Const (nA+nB),
Дополнение
Множество представлено битовым вектором
I ─ A
Алгоритм выполнения этой операции:
for (i = 0; i < m; i++) B[i] = ~ A[i];
И время равно
t = Const ∙N.
Множество представлено одномерным массивом
Для получения результата необходимо из универсума поочередно извлечь все элементы мн-ва А. Отсюда получаем: t = Const×n×N.
Множество представлено упорядоченным массивом
Упорядоченность массивов-носителей не улучшает время выполнения этой операции:
t = Const ∙n∙N.
Эффективность выполнения операций над множествами для различных реализаций
|
|
|
Указаны оценки времени выполнения алгоритма в среднем
| Битовый вектор | Не упорядоч. мн-во | Упорядоч. мн-во | |
| xÎA? | Q(1) | Q(nA) | Q(log(nA)) |
| A + x | Q(1) | Q(nA) | Q(nA) |
| A – x | Q(1) | Q(nA) | Q(nA) |
| A È B | Q(N) | Q(nA∙nB) | Q(nA+nB) |
| А Ç В | Q(N) | Q(nA∙nB) | Q(nA+nB) |
| `A | Q(N) | Q(nA∙N) | Q(N) |
где n - число элементов множества X.
Получение полных наборов комбинаторных объектов. Перестановки
Получение полных наборов комбинаторных объектов (КО) важно для решения многих задач дискретного анализа. Примером могут служить задачи оптимизации на дискретных множествах, при решении которых используются полные наборы КО.
При использовании полных наборов КО используются два вида процедур:
- процедуры, которые генерируют все КО, составляющие полный набор;
- процедуры, которые при каждом вызове выдают очередной КО.
Число перестановок n элементов равно:
Nprm(n) = n! = 1×2×3×... ×n.
Перестановки
Рекурсивная процедура permuts генерирует и выводит на экран все перестановки элементов массива A.
int P; // номер очередной перастановки
void permuts(int* A, int n, int k) // k – номер рекурсивного вызова
{ int i,j;
for (i = k; i < n; i++)
{ swp(A[k], A[i]);
if (i!=k || k == 0) { P++; printf("%2d ",P);
for (j = 0; j < n; j++) printf("%2d ",A[j]); puts("");
}
if (k < n-2) permuts(A, n, k+1);
swp(A[k], A[i]);
}
}
Пример использования процедуры permuts:
