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

Будем считать, что искомый элемент в таблице существует.

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

р(i) = 1

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

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

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

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

24) Метод оптимизации поиска путем (Переупорядочивание таблицы) перестановки найденного элемента в начало списка

Суть этого метода заключается в том, что элемент списка с ключом, равным заданному, становится первым элементом списка, а все остальные сдвигаются.

Этот алгоритм применим как для списков, так и для массивов. Однако не рекомендуется применять его для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.

Алгоритм перестановки в начало списка:

q= nil

p = table

while (p <> nil) do

if key = k(p) then

search = p

if q = nil

then 'перестановка не нужна'

return

endif

nxt(q) = nxt(p)

nxt(p) = table

table = p

return

endif

q = p

p = nxt(p)

endwhile

search = 0

return