Эффективность последовательного поиска
Эффективность любого поиска может оцениваться по количеству сравнений C
аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска.
Эффективность последовательного поиска в массиве:
C = 1 ? n, C = (n + 1)/2.
Эффективность последовательного поиска в списке - то же самое. Хотя по количеству сравнений поиск в связанном списке имеет ту же эффективность, что и поиск в массиве, организация данных в виде массива и списка имеет свои достоинства и недостатки. Целью поиска является выполнение следующих процедур:
1) Найденную запись считать.
2) При отсутствии записи произвести ее вставку в таблицу.
3) Найденную запись удалить.
Первая процедура (собственно поиск) занимает для них одно время. Вторая и третья процедуры для списочной структуры более эффективна (т. к. у массивов надо сдвигать элементы).
Если k - число передвижений элементов в массиве, то k = (n + 1)/2.
