Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

if key = k(j) then
search=j
return
endif
next j
search=0
return

Паскаль:
i:=1;
while (i <= m) and (kind[i] <= key) do
i=i+1;
if i = 1 then low:=1 else low:=pind[i-1];
if i = m+1 then hi:=n else hi:=pind[i]-1;
for j:=low to hi do
if key = k[j] then
begin
search:=j;
exit;
end;
search:=0;
exit;
5.3. Эффективность последовательного поиска

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

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

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

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

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

Желательно, чтобы p(1)?p(2) ?p(3) ?…?p(n).
Это минимизирует количество сравнений, то есть увеличивает эффективность. Так как последовательный поиск начинается с первого элемента, то на это место надо поставить элемент, к которому чаще всего обращаются (с наибольшей вероятностью поиска).
Наиболее часто используются два основных способа автономного переупорядочивания таблиц поиска. Рассмотрим их на примере односвязных списков.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники