Эффективность последовательного поиска
Эффективность любого поиска может оцениваться по количеству сравнений C аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска.
Эффективность последовательного поиска в массиве:
C = 1 n, C = (n + 1)/2.
Эффективность последовательного поиска в списке - то же самое. Хотя по количеству сравнений поиск в связанном списке имеет ту же эффективность, что и поиск в массиве, организация данных в виде массива и списка имеет свои достоинства и недостатки. Целью поиска является выполнение следующих процедур:
1) Найденную запись считать.
2) При отсутствии записи произвести ее вставку в таблицу.
3) Найденную запись удалить.
Первая процедура (собственно поиск) занимает для них одно время. Вторая и третья процедуры для списочной структуры более эффективна (т. к. у массивов надо сдвигать элементы).
Если k - число передвижений элементов в массиве, то k = (n + 1)/2.
5.4. Эффективность индексно-последовательного поиска
Ecли считать равновероятным появление всех случаев, то эффективность поиска можно рассчитать следующим образом:
Введем обозначения: m - размер индекса; m = n / p; p - размер шага
Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1
Продифференцируем Q по p и приравняем производную нулю:
dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0
Отсюда p2=n ; 
Подставив ропт в выражение для Q, получим следующее количество сравнений: Q = 
+1
Порядок эффективности индексно-последовательного поиска O ( 
)
Методы оптимизации поиска
Всегда можно говорить о некотором значении вероятности поиска того или иного элемента в таблице. Считаем, что в таблице данный элемент существует. Тогда вся таблица поиска может быть представлена как система с дискретными состояниями, а вероятность нахождения там искомого элемента - это вероятность p(i) i - го состояния системы.
Количество сравнений при поиске в таблице, представленной как дискретная система, представляет собой математическое ожидание значения дискретной случайной величины, определяемой вероятностями состояний и номерами состояний системы.
Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)
Желательно, чтобы p(1)p(2) p(3) …p(n).
Это минимизирует количество сравнений, то есть увеличивает эффективность. Так как последовательный поиск начинается с первого элемента, то на это место надо поставить элемент, к которому чаще всего обращаются (с наибольшей вероятностью поиска).
Наиболее часто используются два основных способа автономного переупорядочивания таблиц поиска. Рассмотрим их на примере односвязных списков.