- Линейный поиск
-
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину N, то найти решение с точностью до
можно за время
. Т.о. асимптотическая сложность алгоритма —
. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Содержание
Пример
Переменные
и
содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е., в результате каждой проверки область поиска уменьшается на один элемент.
int function LinearSearch (Array A, int L, int R, int Key); begin for X = L to R do if A[X] = Key then return X return -1; // элемент не найден end;
Анализ
Для списка из n элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо n сравнений.
Если искомое значение входит в список k раз и все вхождения равновероятны, то ожидаемое число сравнений
Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно
. Однако, если известно, что оно встречается один раз, то достаточно n - 1 сравнений и среднее число сравнений будет равняться
(для n = 2 это число равняется 1, что соответствует одной конструкции if-then-else).
В любом случае, вычислительная сложность алгоритма O(n).
Приложения
Обычно линейный поиск очень прост в реализации и применим, если список содержит мало элементов, либо в случае одиночного поиска в неупорядоченном списке.
Если предполагается в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например сортировки и последующего использования бинарного поиска, либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.
Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
См. также
Ссылки
Категория:- Алгоритмы поиска
Wikimedia Foundation. 2010.