Структуры данных и модели вычислений


Реализация операций с помощью массива


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

Операция СОЗДАТЬ() осуществляется записью элемента

в ячейку с номером . Время выполнения операции — .

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

Операция НАЙТИ () выдает в качестве

содержимое элемента с номером в массиве . Время выполнения операции — .

При такой реализации разделенных множеств, очевидно, что время выполнения произвольных операций, среди которых операций ОБЪЕДИНИТЬ, есть величина .




Начало  Назад  Вперед



Книжный магазин