Анализ алгоритмов и структур данных. Критерии эффективности алгоритмов.
Отдельное значение составной единицы информации (СЕИ), находящейся в памяти ЭВМ, называется записью. Запись состоит из значений атрибутов, входящих в структуру СЕИ. Множество записей образует массив или файл.
Термин массив обычно используется при рассмотрении данных а оперативной памяти ЭВМ, а термин файл применяется для данных, хранимых на внешних запоминающих устройствах. Как правило файл содержит записи, принадлежащих к 1 и той же СЕИ, хотя в общем случае это не является обязательным.
Организация значений данных – относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями. Организация значений данных может быть линейной и нелинейной. При линейной организации данных каждая запись, кроме первой и последней, связана с первой предыдущей и первой последующей записями. У записей, соответствующих нелинейной организации данных, кол-во предыдущих и последующих записей может быть произвольным.
Среди линейных методов выделяются последовательная и цепная организации данных. При последовательной организации данных записи располагаются в памяти строго 1 за другой, без промежутков, в той последовательности, в которой они обрабатываются. Последовательная организация данных обычно соответствует понятию массив (файл).
С точки зрения показателей длины записи делятся на записи постоянной длины (фиксированной), переменной и неопределенной длины.
Записи фиксированной длины имеют одинаковую, заранее известную длину. Если длины записей неодинаковы, то длина указывается в самой записи – записи переменной длины. Вместо явного указания длины записи можно отмечать окончание записи специальным символом –разделителем, который не должен встречаться среди информационных символов значений записи. Записи, заканчивающиеся разделителем называются записями неопределенной длины.
Для фиксированной длины в массиве адреса задаются следующим образом:
A(i)=A1+(i-1)*L
A(i) – начальный адрес i -й записи,
A1 – начальный адрес первой записи,
L – длина одной записи.
Последовательный массив состоит из записей фиксированной длины, а среди атрибутов записи выделяется только 1 ключевой атрибут. Наличие в записи других (неключевых) атрибутов специально не оговаривается.
Ключевой атрибут обычно бывает атрибутом признаком. Часто требуется поддерживать упорядоченность записей по нескольким именам ключевых признаков. В этом случае среди признаков устанавливается старшинство. Условие упорядоченности записей в массиве (и вообще для линейной организации данных) выглядит следующим образом:
p(i)=p(i+1) – упорядоченность по убыванию.
Критерии эффективности алгоритмов.
-Время поиска данных. Анализируется обычно простейший и наиболее распространенный случай (поиск по совпадению) – найти записи у которых значение ключевого атрибута = заранее известной величине q.
-Время корректировки данных. Из всех возможных вариантов корректировки учитывается включение и исключение одной записи.
-Объем дополнительной памяти, расходуемый под служебную информацию (Н-р: адреса связи).
-Время формирования данных, т.е. время создания в памяти ЭВМ так или иначе упорядоченного представления данных.
При анализе алгоритмов необходим еще ряд допущений, обеспечивающих использование равномерного распределения вероятностей для всех случайных величин, описывающих работу алгоритма, в том числе:
-распределение значение ключевых атрибутов в массиве из М-записей – равномерное.
-значение q при поиске совпадений выбрано случайно: это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива.
-положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что при поиске.
Массив, обладающий наибольшей неопределенностью своего состояния – случайный массив. Все его М! состояний равновозможны. Т.о. минимальное число сравнений, необходимое для упорядочения массива из М записей определяется как С=log M!, что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа «да, нет». Условимся, что ф-я log обозначает логарифм по основанию 2.
После преобразований по формуле Стерлинга:
С=М*(log М-1,43)
В анализе алгоритмов принято учитывать в подобных формулах лишь те слагаемые, которые ощутимо влияют на общую сумму (разность).
С пропорционально М logМ
Т пропорционально М logМ