«ТЭИС» Великанова

Когда интервал поиска впервые станет меньше 1, применяемая схе-ма округления результата деления даст нулевой интервал и поиск закончится. Это соответствует нера-венству M/(2^Cm)<=1 (Ст – макси-мальное число сравнений, знак ^ обозначает возведение в степень), откуда Cm~logM. Во всех трех случаях время поиска является функцией от числа записей М. Конкретные выражения составляют: ? Т1~М или T1=k1* М - для последовательного поиска; ? T2~ или Т1 =k2* - для двухступенчатого поиска; ? T3~log М или Т3= k3*log M - для бинарного поиска. Пересылка затрагивает примерно половину записей массива. Время пересылки одной записи пропорци-онально ее длине: Tk ~ log М + М • L. Через L обозначена длина одной записи массива. В формуле для Tk второе слагаемое по величине всег-да значительно превышает первое, поэтому можно считать Tk ~ M • L. Списком называется множество записей, занимающих произвольные участки памя-ти, последовательность обработки кото-рых задается с помощью адресов связи. Адресом связи некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрас-танием значений ключа в записях. Возможны два способа организации списка — совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют одно целое (а), и раздельное, когда имеется списковая организация адресов связи и последовательное хранение собственной информации (б). При формировании упорядоченного списка записей возможны два вари-анта: ? вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу; ? создать сначала неупорядоченный список, а затем отсортировать его. Организация двунаправленного (а) и кольцевого (б) списков : Цепным каталогом называется сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список об-рабатываемых записей и список свободных по-зиций памяти. Адрес связи, отмечающий первую обра-батываемую запись, называется указателем списка. Адрес связи, отмечающий первую свобод-ную позицию памяти называется указателем свободной памяти. Адрес связи последней записи (или послед-ней позиции свободной памяти) в списке называ-ется концом списка, и в этой книге отмечается нулевым значением. Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом: на 1-м уровне расположена только одна запись (корень дерева), к любой записи 1-го уровня ведет адрес связи только от одной записи уровня i=1. Представление древовидной организации данных в памяти ЭВМ : Оценки методов организации данных: МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ (продолжение). План лекции : ? Анализ алгоритмов и структур данных в ЭИС. ? Методы ускорения доступа к данным. ? Организация данных во внешней памяти ЭВМ.