Сложность типовых операций при работе с линейными структурами данных

Структуры данных оказывают существенное влияние на методы решения задач и сложность типовых алгоритмов. Можно привести оценки сложности основных операций с линейными структурами данных, таких как добавление, удаление и поиск элемента по индексу или ключу. Элементарными операциями, в данном случае, являются операции сравнения, перебора, вычисления адреса или перестановки элементов набора структуры данных. В сводной таблице, помимо верхней оценки сложности, также приведены соответствующие перечисленным структурам данных компоненты библиотеки BCL. Таким образом, основные линейные структуры данных уже есть в готовом виде и доступны всем разработчикам программного обеспечения на платформе Microsoft .NET Framework.

Структура	Вставка	Удаление	Поиск	Компонент BCL
Массив	-	-	O(1)	Базовый тип Array
Список	O(N)	O(N)	O(N)	List<T>
Связанный список	O(1)	O(1)	O(N)	LinkedList<T>
Стек	O(1) (добавление в конец)	O(1) (удаление последнего)	O(N)	Stack<T>
Очередь	O(1) (добавление в конец)	O(1) (удаление первого)	O(N)	Queue<T>
Хэш-таблица	O(1)	O(1)	O(1)	Dictionary<TKey, TValue

Представление данных в памяти эвм

Данные хранятся в памяти компьютера. При этом различают логическую (в программе) и физическую (в памяти) структуры данных. Эффективность алгоритмов зависит от того, насколько согласованы обе эти структуры.

Память современных ЭВМ имеет линейную организацию. Она представляет собой последовательность ячеек (строк). Наименьшей адресуемой единицей является байт. Данные имеют размер, равный 1 или нескольким байтам. Память для них выделяется компилятором.

Так для простых (скалярных) типов данных в разных компьютерах и языках программирования используются следующие объемы памяти.

1. Булевский тип – 1 байт (причем для задания значений «истина» или «ложь» достаточно 1 бита, оно берется из младшего разряда байта);

2. Символьный – 1 байт ( в java – 2 байта);

3. Целочисленный – 2 или 4 байта;

4. Вещественный – 4 или 8 байт;

5. Строковый – до 256 байт.

Сложные типы могут размещаться в смежных ячейках памяти или произвольно.

Например массивы, как уже отмечалось, располагаются в последовательных ячейках. Для нахождения физического адреса любого элемента используется адрес начального элемента и смещение (индекс).

Имя

Адрес (элемент(index)) = Начало + размер_ячейки * index.

Такой подход облегчает работу с массивом. Его элементы могут обрабатываться последовательно или в любом порядке.

Линейные списки обычно располагаются в памяти последовательно (как массивы). Этот порядок часто нарушается при выполнении операций вставок и удалений.

Связные списки требуют дополнительного объема памяти для размещения таблицы связей. В них более просто реализуются операции вставки и удаления элементов.

Деревья представляют собой связные списки соответствующей структуры. Они хранятся аналогично.

Графы и таблицы принято представлять таблицами связности, смежности и др., т.е. двумерными массивами.

Файлы обычно описываются файловой переменной некоторого типа. Его элементы располагаются последовательно, как правило, на внешних запоминающих устройствах.

Важной особенностью рассматриваемых структур является то, что память для скалярных переменных, массивов и файловой переменной выделяется до выполнения программы на все время ее работы. Такой способ называют статическим. Для списков и деревьев память выделяется непосредственно во время выполнения программы. Такой способ называют динамическим.

Наиболее простой и естественный способ обработки данных всех типов – последовательный. Массивы, таблицы и файлы могут также обрабатываться в любом (произвольном) порядке. Для списков используется только последовательный доступ. При этом добавление и удаление элементов возможно в любом месте списка.