Линейный поиск


Линейный поиск

Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Если отрезок имеет длину N, то найти решение с точностью до \epsilon можно за время N\over\epsilon. Т.о. асимптотическая сложность алгоритма — O(n). В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.

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

Содержание

Пример

Переменные L и R содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е., в результате каждой проверки область поиска уменьшается на один элемент.

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 раз и все вхождения равновероятны, то ожидаемое число сравнений


\begin{cases} 
  n                   & k = 0 \\[5pt]
  \displaystyle\frac{n + 1}{k + 1} & 1 \le k \le n.
\end{cases}

Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно \frac{n + 1}2. Однако, если известно, что оно встречается один раз, то достаточно n - 1 сравнений и среднее число сравнений будет равняться

\displaystyle\frac{(n + 2)(n-1)}{2n}

(для 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.

Смотреть что такое "Линейный поиск" в других словарях:

  • Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов. Содержание 1 Описание 2 Свойства …   Википедия

  • Поиск количественных соотношений структура-свойство — Поиск количественных соотношений структура свойство  процедура построения моделей, позволяющих по структурам химических соединений предсказывать их разнообразные свойства. За моделями, позволяющими прогнозировать количественные… …   Википедия

  • Линейный криптоанализ — В криптографии линейным криптоанализом называется метод криптоаналитического вскрытия, использующий линейные приближения для описания работы шифра. Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (Mitsuru Matsui).… …   Википедия

  • Линейный корабль «Бисмарк» — «Бисмарк» Bismarck Линкор «Бисмарк», 1940 год Основная информация Тип Линкор …   Википедия

  • Линейный корабль Слава — Необходимо перенести содержимое этой статьи в статью «Слава (броненосец)». Вы можете помочь проекту, объединив статьи. В случае необходимости обсуждения целесообразности объединения, замените этот шаблон на шаблон {{к объединению}} …   Википедия

  • ПОИСК ВЗАИМОДЕЙСТВИЙ — одна из наиболее распространенных задач анализа данных (см.) в социологии, состоящая в выявлении взаимодействий признаков (см.). Проблема П.в. особую актуальность имеет для социологии, экономики и др. поведенческих наук, анализ данных в к рых… …   Российская социологическая энциклопедия

  • Интерполирующий поиск — основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному… …   Википедия

  • Двоичный поиск — Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной… …   Википедия

  • Троичный поиск — (Тернарный поиск) это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой,… …   Википедия

  • Преображение Господне (линейный корабль) — «Преображение Господне» «Слава Екатерины» Служба …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.