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

       

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


Эффективность любого поиска может оцениваться по количеству сравнений C

аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска.

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

C = 1 ? n, C = (n + 1)/2.

Эффективность последовательного поиска в списке - то же самое. Хотя по количеству сравнений поиск в связанном списке имеет ту же эффективность, что и поиск в массиве, организация данных в виде массива и списка имеет свои достоинства и недостатки. Целью поиска является выполнение следующих процедур:

1) Найденную запись считать.

2) При отсутствии записи произвести ее вставку в таблицу.

3) Найденную запись удалить.

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

Если k - число передвижений элементов в массиве, то k = (n + 1)/2.



Содержание раздела