Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 2 )

Типы данных можно также разделить:

- на типы данных линейной структуры;

- на типы данных нелинейной структуры.

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

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

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

Массив – это структура данных, имеющих один и тот же тип, с прямым доступом посредством целого индекса.

Важнейшей операцией при работе с массивами является организация доступа к элементам.

Для доступа к элементу на логическом (пользовательском) уровне достаточно указать имя массива и индекс элемента.

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

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

Хеш-таблица сохраняет данные, связанные с ключом. Ключ трансформируется в целый индекс, используемый для нахождения данных. Ключ необязательно должен быть целым числом, например, в качестве ключа может использоваться имя.

Структура данных, называемая словарем, состоит из набора пар «ключ-значение», называемых ассоциациями.

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

Типы данных линейной структуры с последовательным доступом к данным являются динамическими структурами данных и характеризуются следующими свойствами:

- непостоянством и непредсказуемостью размера;

- отсутствием физической смежности элементов структуры в памяти.

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

В упорядоченном линейном списке данные упорядочены относительно друг друга ( 3, 5, 11, 18, 33).

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

Очередь –это линейный список с доступом только в начале и в конце списка. Элементы вставляются в конец списка и удаляются из начала (первый пришел - первый ушел).

Очередь приоритетов – это список типа очередь; при удалении объекта из списка определяется элемент с наивысшим приоритетом.

Файл – это последовательность байтов, приравниваемая к потоку (последовательность байтов, перемещаемая от одного устройства к другому). Прямой доступ осуществляется только к дисковому файлу.

Иерархическая структура – это совокупность элементов, которые разделяются по уровням. Элементы на данном уровне могут иметь несколько наследников на следующем уровне.

Дерево – это структура данных, в которой все элементы происходят от одного источника, называемого корнем. Каждый элемент, за исключением корня, имеет единственного предка.

Пирамида – это особая версия дерева, в котором самый маленький (большой) элемент всегда занимает корневой узел.

Группа представляет собой нелинейные структуры, которые содержат элементы без какого-либо упорядочения.

Множество – эта структура данных, которая находит применение, когда данные являются неупорядоченными и каждый элемент данных является единственным в своем роде, уникальным.

Граф – это структура данных, задающая набор вершин и набор связей, соединяющих вершины.

Сеть – это особая форма графа, которая присваивает вес каждой связи.

Операции над структурами данных

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

- обход структуры: доступ к каждому элементу структуры с целью его последующей обработки;

- поиск: нахождение места расположения элемента с данным значением;

- вставка: включение нового элемента в структуру;

- удаление: исключение элемента из структуры.

Анализ алгоритмов. Сортировка и поиск

Анализ алгоритмов. Время выполнения программ

Для сравнения разных алгоритмов, предназначенных для решения одной задачи, для приблизительной оценки времени выполнения программы применяется математический анализ алгоритмов.

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

Быть простым для понимания, перевода в программный код и отладки. Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.

На время выполнения программы влияют следующие факторы:

Ввод исходной информации в программу. Качество скомпилированного кода исполняемой программы. Машинные инструкции, используемые для выполнения программы. Временнaя сложность алгоритма соответствующей программы.

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

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

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

Следует отдавать предпочтение программам с наименьшей степенью роста времени выполнения. Это объясняется тем, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере.

На рис. 1.1 показаны функции времени выполнения для четырех программ с различной временной сложностью.

Рис. 1.1. Функции времени выполнения четырех программ

Сравнение порядков временной сложности представлено в следующей таблице:

2	1	2	4	8	4
8	3	24	64	512	256
16	4	64	256	4096	65536

Следует избегать использования кубических и экспоненциальных алгоритмов при немалых значениях n.

Теоретическое нахождение времени выполнения программ – сложная математическая задача, для ее решения необходимо знать несколько базовых принципов.

Для начала рассмотрим три важных правила:

1) постоянные множители не имеют значения для определения порядка временной сложности, т. е. O(k*f)=O(f);

2) Правило произведений: порядок временной сложности произведения двух функций равен произведению их сложностей: O(fg)=O(f)O(g);

3) Правило сумм: порядок временной сложности суммы функций равен порядку максимального из слагаемых): .

Правила анализа программ:

Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О(1). Время выполнения последовательности операторов определяется с помощью правила сумм. Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок О(1). Время для всей конструкции условия состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь). Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок О(1)). Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно.

Пример:

Рассмотрим следующую программу сортировки:

…
(1)  for (int i=0; i<n-1; i++)
(2)        for (int j=n-1; j>i; j--)
(3)         if (a[j-1]>a[j]) {
(4)                 temp=a[j-1];
(5)                        a[j-1]=a[j];
(6)                        a[j]=temp;
        }
…

Число элементов n, подлежащих сортировке, служит мерой объема входных данных.

Операторы (4) – (6) имеют время выполнения порядка О(1). В соответствии с правилом сумм время выполнения этой группы операторов равно O(max(1, 1, 1))=O(1).

Для оператора if проверка логического выражения занимает время порядка О(1). Мы предполагаем, что операторы (4) – (6) в теле условного оператора выполняются и время их выполнения О(1). Таким образом, время выполнения группы операторов (3) – (6) имеет порядок О(1).

Рассмотрим группу (2) – (6) операторов внутреннего цикла. Для операторов (2) – (6) время выполнения на каждой итерации имеет порядок О(1). Цикл выполняется n-i раз, поэтому по правилу произведений общее время выполнения цикла имеет порядок O((n-i)*1) = O(n-i).

Рассмотрим внешний цикл. Оператор (1) выполняется n-1 раз, поэтому суммарное время выполнения программы ограничено выражением

,

которое имеет порядок.

Традиционно значение О-функции для алгоритма структур данных выбирается среди небольшого набора полиномиальных, логарифмических и экспоненциальных функций.