Линейный поиск: различия между версиями

34 байта добавлено ,  14 лет назад
нет описания правки
[непроверенная версия][непроверенная версия]
(+ {{изолированная статья|кольцо2сирота0}} при помощи AWB)
Нет описания правки
{{изолированная статья|кольцо2сирота0}}
{{викифицировать}}
'''Линейный, последовательный поиск''' — [[алгоритм]] нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от [[двоичный поиск|двоичного поиска]], не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
 
Если отрезок имеет длину N, то найти решение с точностью до <math>\epsilon</math> можно за время <math>N\over\epsilon</math>. Т.о. асимптотическая сложность алгоритма - <math>O(n)</math>. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
Анонимный участник