Сравнение последовательного и связанного распределения

Критерий

Последовательные распр.

Связанные распр.

1.Доступность к элементу.

Массив

K

адрес(Хк)=адрес(Х1) + К*размер(Хi)

O(1)

Реализует модель с произвольным доступом к элементу

ЛСС

O(n)

Реализует модель с последовательным доступом.

2.Расположение в памяти

Область должна быть единой , однако как правило операционная система (ОС) память выделяет по страничное, при этом размер страницы может быть меньше чем требуемый размер под страницу.

Последовательность областей – таблицы дескрипторов областей, выделенных под массив.

Задается под ОС, следует разделять динамический и статический массив.

Статические элементы должны умещаться в 64Мб, а если нет – то создаются динамические массивы, которым доступно всё ОЗУ ОС. Доступ к элементу динамического массива на порядок медленнее доступа к статическому массиву.

Это изначально динамический список. Поэтому ему доступно всё адресное пространство ОС.

3.Добавление элемента

Пусть требуется добавить новый элемент в позиции с номером k.

О(N)

Вставка заключается в трех шагах

1. Выделение памяти под новый элемент

4.Удаление элемента – аналогично

О(N)

5.Объединение или соединение.

=

О(N)

Объединение ЛСС заключается в том, что вместо признака конца первого списка записывает адрес первого элемента первого списка. Казалось что доступ к последнему элементу первого списка осуществится за О(N). Однако для экономии операций, если алгоритм ориентирован на регулярное слияние, то кроме головы можно хранить и хвост а’ и в’, которые указывают на последний элемент. Тогда операция добавления элемента в конец списка будет, осуществляется O(1).