ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ ПОИСКА

Основными асимптотиками, характеризующими алгоритмы поиска, являются емкостная и операционная сложности.

Емкостная сложность отражает объем памяти ЭВМ, необходимый для хранения таблицы. Операционная сложность показывает число сравнений ключей, необходимых для осуществления поиска.

При разработке или выборе алгоритма поиска наибольший интерес представляют не асимптотические, а фактические оценки трудоемкости алгоритмов при реальных значениях длины входа п, а не при п —> °° .

Поэтому традиционной мерой трудоемкости алгоритмов поиска является среднее количество необходимых сравнений ключей (С), рассматриваемое как функция длины п таблицы, в которой осуществляется поиск.

ПОСЛЕДОВАТЕЛЬНЫЙ (ЛИНЕЙНЫЙ) ПОИСК

Линейный поиск используется в том случае, если никакой дополнительной информации о разыскиваемых данных нет. Применяется к таблице, организованной как массив или как список. Последовательность шагов поиска элемента с ключом х в непустой таблице имеет вид (Search — адрес искомого элемента, Search=0, если элемент не найден):

• для массива:

i:=1;

while (ix) do lnc(i); if a[i].Key=x then Search:=i

else Search:=0; //i-n и a[n].Key <> x

• для списка:

ltem:= Head;

while (ltem^A.Next<>nil) and (ltem^A.Key<>x) do ltem:= ltem^A.Next; if ltem^A.Key=x then Search:= Item else Search:=nil;

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

Поиск с включением реализуется следующим образом:

• для массива необходимо выделить достаточное место в памяти (для последующих включений):

i:=1:

while (ix) do lnc(i); if a[i].Key<>x

then begin //элемент в списке отсутствует

i:=n+1;

a[i].Key:=x; // запись в a[i] ключа

// запись в ар] других полей n:=i;

end;

Search:=i;

• для списка:

ltem:= Head;

while (ltem^A.Next<>nil) and (ltem^A.Key<>x) do ltem:= ltem^A.Next;

if ltem^A.Key<>x then begin

// элемент в списке отсутствует

New(ltem^A.Next); ltem:=ltem^A.Next; ltem^A.Key:=x; //запись в Item^A ключа

//запись в Item^A других полей

ltem^A.Next:=nil;

end;

Search:=ltem;

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

Для этого в конец массива или списка помещается элемент с ключом х, называемый «барьером», так как он охраняет нас от перехода за пределы массива. Последовательность шагов поиска имеет вид:

• для массива:

а[п+1].Кеу:=х; //барьер

i:=1;

while a[i].Key<>x do lnc(i); if i

then Search:=i else Search:=0;

• для списка необходимо определить указатель Rear на конец списка (для эффективного включения в конец списка):

InsertRear(x); //включение х в конец списка - барьер ltem:= Head;

while ltem^A.Key<>x do ltem:= ltem^A.Next; if ltem^A.Next<>nil then Search:=ltem else Search:=nil;