Линейный поиск: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
м r2.7.1) (робот добавил: hy:Գծային փնտրում |
м r2.7.1) (робот изменил: hy:Գծային փնտրում/Ավազարկղ |
||
Строка 52: | Строка 52: | ||
[[en:Linear search]] |
[[en:Linear search]] |
||
[[fi:Peräkkäishaku]] |
[[fi:Peräkkäishaku]] |
||
[[hy:Գծային փնտրում]] |
[[hy:Գծային փնտրում/Ավազարկղ]] |
||
[[id:Pencarian linear]] |
[[id:Pencarian linear]] |
||
[[is:Línuleg leit]] |
[[is:Línuleg leit]] |
Версия от 05:04, 30 марта 2012
Эту статью необходимо исправить в соответствии с правилом Википедии об оформлении статей. |
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину 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;
Литература
- Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
См. также
Ссылки
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |