Эффективность последовательного поиска

Эффективность любого поиска может оцениваться по количеству сравнений 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 ; Эффективность последовательного поиска - student2.ru

Подставив ропт в выражение для Q, получим следующее количество сравнений: Q = Эффективность последовательного поиска - student2.ru +1

Порядок эффективности индексно-последовательного поиска O ( Эффективность последовательного поиска - student2.ru )

Методы оптимизации поиска

Всегда можно говорить о некотором значении вероятности поиска того или иного элемента в таблице. Считаем, что в таблице данный элемент существует. Тогда вся таблица поиска может быть представлена как система с дискретными состояниями, а вероятность нахождения там искомого элемента - это вероятность p(i) i - го состояния системы.

Эффективность последовательного поиска - student2.ru

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

Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)

Желательно, чтобы p(1)p(2) p(3) …p(n).

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

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

Наши рекомендации