2015-05-22
356
Множество представлено битовым вектором
Проверка отношения xÎA. Под А будем понимать заданное множество и, в то же время, бинарный код этого множества. Эта операция сводится к считыванию из битового вектора значения бита номер x. Обозначим его через qx.
Пусть M = |U|. В качестве массива-носителя B бит. вектора выберем массив с элементами типа unsigned short (16 бит). Размер n массива B будет равным:
m = M/16+1. (1)
Определим константу bit:
const unsigned short bit = 0x8000;
Она содержит единственный единичный бит в первой слева позиции 16-битового значения. Вычисление qx сводится к выполнению след. операций:
j=i/16; k=i%16;
qx = B[j] & (bit>>k);
Отсюда время выполнения этой операции равно: t = Const.
Это время не зависит ни от размера множества А, ни от размера универсума U.
Множество представлено одномерным массивом
Проверка отношения xÎA. Значение x поочередно сравнивается с элементами мн-ва A. Отсюда:
t = Const ∙n.
где n = |A|.
Множество представлено упорядоченным массивом
Использование алгоритма бинарного поиска дает:
|
|
|
t = Const ∙log(n).
Включение
Множество представлено битовым вектором
Рассмотрим алгоритм включения элемента x в множество A, т.е. алгоритм выполнения операции A+x, где А – множество, x – добавляемый элемент. Операция сводится к установке бита с номером, равным x, в 1. Вычисления сводятся к выполнению след. операций:
j=i/16; k=i%16;
qx = B[j] || (bit>>k);
Отсюда время выполнения этой операции также равно: t = Const.
Множество представлено одномерным массивом
Операция A+x. Включаемый элемент x вносится в мн-во A в том случае, если он там не содержится. Отсюда имеем:
t = Const ∙n.
Множество представлено упорядоченным массивом
Эта операция содержит два шага:
- проверить, содержится ли заданное x в мн-ве А,
- если содержится, то вставить его в А, не нарушая порядка.
Определяющим (более медленным) является второй шаг. Для времени имеем:
t = Const ∙n.
