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

       

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


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

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

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

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

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

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

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



Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий