Теория экономических информационных систем


Теория экономических информационных систем - стр. 61


С = log М!,

что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа: да – нет (логарифм по основанию 2).

Сравнение методов организации данных             Табл. 1.

 

 

Методы организации данных

          Лучший метод

Критерии оценки

последовательный

цепной

бинарное дерево

Время формирования

~ М log М

~ М log М

~ М log М

цепной, бинарное дерево

Время поиска

~ log М

~ М

~ log М

последовательный, бинарное дерево

Время корректировки

~ М

~ М

~ log М

бинарное дерево

Объем дополнительной памяти

0

~ М

~ М

последовательный

 

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

Поиск в последовательном массиве

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

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

Рассмотрим простейший вариант ступенчатого поиска – одноступенчатый или последовательный поиск. Искомое значение q сравнивается с ключом первой записи, если значения не совпадают, с ключом второй записи и т.


Начало  Назад  Вперед



Книжный магазин