ЛЕКЦИЯ 14. КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПОИСКА. ПОИСК В ЛИНЕЙНЫХ СТРУКТУРАХ ДАННЫХ
Цели и задачи лекции..Ознакомиться с алгоритмами поиска данных в линейных структурах.
Основные рассматриваемые вопросы:последовательный поиск, бинарный поиск, поиск методом экстраполяций, спообы коррекции алгоритмов поиска.
Поиск в линейных структурах данных
Говоря о поиске, мы будем иметь в виду некий массив данных, а искать будем определенный элемент в этом массиве. Оптимальность поиска для простоты определим очень конкретно - это скорость работы алгоритма.
Какой алгоритм , из множества известных сейчас, самый быстрый?Ответа на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи, которую нам придется решать.
Общая классификация алгоритмов поиска
· Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность.
· Так же методы поиска можно разделить на методы, использующие истинные ключи и на методы, работающие по преобразованным ключам. В данном случае "ключем" называют то значение, которое мы ищем.
· методы основанные на сравнении самих значенийи методы, основанные на ихцифровых свойствах. Так называемые методы хэширования.
Оптимальность метода поиска зависит от размера массива, в котором мы ищем! Прямой перебор (последовательный поиск) всех значений прост в понимании, легок в исполнении и достаточно быстр на малых массивах данных. Итак, все это в совокупности позволяет сказать, что метод прямого перебора оптимален для малых массивов.
Если же массив данных достаточно велик, то оптимальность поиска достигается предварительной сортировкой значений в массиве.
|
|
|
Линейный поиск (последовательный)
Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
Элемент найден, т. е. а[i ]= x.
Весь массив просмотрен и совпадения не обнаружено.
Это дает нам линейный алгоритм:
Алгоритм 1.
i:=0;
while (i<N) and (а[i]<>х) do i:=i+1
Следует обратить внимание, что если элемент найден, то он найден вместе с минимально возможным индексом, т. е. это первый из таких элементов. Равенство i=N свидетельствует, что совпадения не существует.
Очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
|
|
|
На каждом шаге алгоритма осуществляется увеличение индекса и вычисление логического выражения. Можно упростить шаг алгоритма, если упростить логическое выражение, которое состоит из двух членов. Это упрощение осуществляется путем формулирования логического выражения из одного члена, но при этом необходимо гарантировать, что совпадение произойдет всегда. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Такой вспомогательный элемент называется барьером. Теперь массив будет описан так:
а: array[0..N] of integer
и алгоритм линейного поиска с барьером выглядит следующим образом:
Алгоритм 2.
a[N]:=x; i:=0;
while a[i]<>x do i:=i+1
Ясно, что равенство i=N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.
Поиск делением пополам (двоичный поиск, бинарный поиск)
Поиск можно сделать значительно более эффективным, если данные будут упорядочены. Поэтому приведем алгоритм поиска делением пополам, основанный на знании того, что массив A упорядочен, т. е. удовлетворяет условию
Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то делается вывод, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Выбор m совершенно не влияет на корректность алгоритма, но влияет на его эффективность. Очевидно, что чем большее количество элементов исключается на каждом шаге алгоритма, тем этот алгоритм эффективнее. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива.
|
|
|
При каждом сравнении , мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.
Рис.2.1. Поиск делением пополам
В этом алгоритме используются две индексные переменные L и R, которые отмечают соответственно левый и правый конец секции массива a, где еще может быть обнаружен требуемый элемент.
Алгоритм 1.
L:=0; R:=N-1; Found:=false;
while(L<=R) and not Found do begin
m:=(L+R) div 2;
if a[m]=x then begin
Found:=true
end else begin
if a[m]<x then L:=m+1 else R:=m-1
end
end;
Максимальное число сравнений для этого алгоритма равно log n, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, где ожидаемое число сравнений N/2.
|
|
|
Эффективность несколько улучшается, если поменять местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенный выигрыш даст отказ от окончания поиска при фиксации совпадения. На первый взгляд это кажется странным, однако, при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами (число шагов в худшем случае равно logN).
Алгоритм 2.
L:=0; R:=N;
while L<R do begin
m:=(L+R) div 2;
if а[m]<x then L:=m+1 else R:=m
end.
Выполнение условия L=R еще не свидетельствует о нахождении требуемого элемента. Здесь требуется дополнительная проверка. Также, необходимо учитывать, что элемент a[R] в сравнениях никогда не участвует. Следовательно, и здесь необходима дополнительная проверка на равенство a[R]=x. Следует отметить, что эти проверки выполняются однократно.
Приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.
Поиск методом Фибоначчи
Рассмотрим его исключительно из академического интереса. Эффективность его немного выше, чем у поиска по Бинарному дереву, хотя так же пропорциональна Log(2)N.
Суть метода в том, что сравнивая наше искомое значение с очередным значением в массиве , мы не делим пополам новую зону поиска , как в бинарном поиске, а отступаем от предыдущего значения, с которым сравнивали, в нужную сторону на число Фибоначчи. Метод Фибоначчи включает в себя только такие арифметические операции, как сложение и вычитание, нет необходимости в делении на 2, тем самым экономится процессорное время.
Дата добавления: 2018-05-02; просмотров: 1974; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!