Структуры данных и модели вычислений
Реализация операций с помощью массива
Обозначим через массив длины , с помощью которого будем представлять коллекцию. Пустая коллекция представляется массивом, заполненным нулями.
Операция СОЗДАТЬ() осуществляется записью элемента
в ячейку с номером . Время выполнения операции — .
Операция ОБЪЕДИНИТЬ() осуществляется следующим образом. Просматриваются элементы массива , и в те ячейки, в которых было записано имя , заносится новое имя — . Следовательно, именем вновь образованного подмножества будет , а перестанет быть именем какого-либо подмножества. Очевидно, время выполнения этой операции — .
Операция НАЙТИ () выдает в качестве
содержимое элемента с номером в массиве . Время выполнения операции — .
При такой реализации разделенных множеств, очевидно, что время выполнения произвольных операций, среди которых операций ОБЪЕДИНИТЬ, есть величина .
