Фундаментальные алгоритмы и структуры данных в Delphi | страница 36

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

До сих пор мы рассматривали только преимущества массивов, но хотелось бы знать и об их недостатках. Первый недостаток связан с операциями вставки и удаления элементов. Что происходит, если, например, в массив необходимо вставить новый элемент с индексом n? В общем случае, все элементы с индексами, начиная с n и до конца массива, потребуется переместить на одну позицию, чтобы освободить место под новый элемент. А фактически выполняется следующий блок кода:

{сначала освободить место под новый элемент}

for i := LastElement downto N do

MyArray[i+1] := MyArray[i];

{вставить новый элемент в позицию с индексом N}

MyArray[N] := NewElement;

{увеличить значение длины массива на единицу}

inc(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Рисунок 2.1. Вставка в массив нового элемента

Рисунок 2.2. Удаление элемента из массива

Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества элементов в самом массиве. Чем больше количество элементов, которые необходимо переместить, тем больше времени потребуется на выполнение операции. То есть, время, требуемое на выполнение цикла For, будет пропорционально количеству элементов в массиве. Другими словами, вставка нового элемента в массив принадлежит к классу операций O(n).

Тот же ход рассуждений справедлив и для операции удаления элемента из массива. Но в этом случае удаление элемента с индексом n означает, что элементы, начиная с индекса n + 1 и до конца массива, будут перенесены на одну позицию к началу массива, чтобы "закрыть" образовавшуюся от удаления элемента "дыру". Как и в случае со вставкой, удаление принадлежит к классу операций O(n).

{удалить элемент, переместив следующие за ним элементы на одну позицию вперед}

for i := N+ 1 to LastElementIndex do

MyArray[i-1] := MyArray[i];

{уменьшить значение длины массива на единицу}

dec(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

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