Линейный поиск: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Голем (обсуждение | вклад) + {{изолированная статья|кольцо2сирота0}} при помощи AWB |
Нет описания правки |
||
Строка 1: | Строка 1: | ||
{{изолированная статья|кольцо2сирота0}} |
{{изолированная статья|кольцо2сирота0}} |
||
{{викифицировать}} |
{{викифицировать}} |
||
'''Линейный поиск''' — [[алгоритм]] нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от [[двоичный поиск|двоичного поиска]], не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. |
'''Линейный, последовательный поиск''' — [[алгоритм]] нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от [[двоичный поиск|двоичного поиска]], не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. |
||
Если отрезок имеет длину N, то найти решение с точностью до <math>\epsilon</math> можно за время <math>N\over\epsilon</math>. Т.о. асимптотическая сложность алгоритма - <math>O(n)</math>. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума. |
Если отрезок имеет длину N, то найти решение с точностью до <math>\epsilon</math> можно за время <math>N\over\epsilon</math>. Т.о. асимптотическая сложность алгоритма - <math>O(n)</math>. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума. |
Версия от 12:27, 6 января 2008
На эту статью не ссылаются другие статьи Википедии. |
Эту статью необходимо исправить в соответствии с правилом Википедии об оформлении статей. |
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину N, то найти решение с точностью до можно за время . Т.о. асимптотическая сложность алгоритма - . В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Пример
Переменные и содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.о., в результате каждой проверки область поиска уменьшается на один элемент.
int function LinearSearch (Array A, int L, int R, int Key); begin for X = L to R do begin if A[X] = Key then return X end; return -1; // элемент не найден end;
Ссылки
Литература
- Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
Это заготовка статьи. Помогите Википедии, дополнив её. |