2.2. ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ

Обычно списки применяются для представления множеств. При этом объем памяти, необходимый для представления множества, пропорционален числу его элементов. Время, требуемое для выполнения операции над множествами, зависит от природы операции. Например, пусть два множества. Операция требует времени, по крайней мере пропорционального сумме размеров этих множеств, поскольку как список, представляющий А, так и список, представляющий В, надо просмотреть хотя бы один раз.

Подобным же образом операция требует времени, пропорционального сумме размеров множеств, поскольку надо выделить элементы, входящие в оба множества, и вычеркнуть один экземпляр каждого такого элемента. Если же не пересекаются, можно найти за время, не зависящее от размера Для этого достаточно сделать конкатенацию списков, представляющих Задача объединения двух непересекающихся множеств усложняется, если необходимо быстро определять, входит ли данный элемент в данное множество. Этот вопрос подробно обсуждается в разд. 4.6 и 4.7.

Другой способ представления множества, отличный от представления его в виде списка, — представление в виде двоичного (битового) вектора. Пусть универсальное множество (т. е. все рассматриваемые множества являются его подмножествами), состоящее из элементов. Линейно упорядочим его. Подмножество представляется в виде вектора из битов, такого, что разряд в равен 1 тогда и только тогда, когда элемент множества принадлежит Будем называть характеристическим вектором для

Представление в виде двоичного вектора удобнее тем, что можно определять принадлежность элемента множества данному множеству за время, не зависящее от размера данного множества. Более того, основные операции над множествами, такие, как объединение и пересечение, можно осуществить как операции над двоичными векторами.

Если мы не хотим считать операции над двоичными векторами первичными (т. е. выполняемыми за единицу времени), то можно с таким же успехом вместо характеристического вектора определить массив для которого тогда и только тогда, когда -й

элемент множества принадлежит При таком представлении все еще легко выяснять, принадлежит ли данный элемент данному множеству. Недостаток этого представления заключается в том, что объединение и пересечение занимают время, пропорциональное а не размерам рассматриваемых множеств. Подобно этому память, требуемая для хранения множества пропорциональна а не