Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти вопросы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны )
|
Класс | Алгоритм поиска |
---|---|
Наихудшая производительность | О ( п ) |
Лучшая производительность | О (1) |
Средняя производительность | O ( п / 2 ) |
Сложность пространства в наихудшем случае | O (1) итеративный |
В информатике , линейный поиск или последовательный поиск представляет собой метод для нахождения элемента в списке . Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или пока не будет выполнен поиск по всему списку. [1]
Линейный поиск выполняется в худшем случае за линейное время и выполняет не более n сравнений, где n - длина списка. Если каждый элемент в равной степени вероятно, будут найдены, то линейный поиск имеет средний случай п + 1 / 2 сравнений, но средний случай может быть затронута , если поисковые вероятности для каждого элемента изменяются. Линейный поиск редко бывает практичным, потому что другие алгоритмы и схемы поиска, такие как алгоритм двоичного поиска и хэш-таблицы , позволяют значительно быстрее искать все, кроме коротких списков. [2]
Линейный поиск последовательно проверяет каждый элемент списка, пока не найдет элемент, соответствующий целевому значению. Если алгоритм достигает конца списка, поиск завершается неудачно. [1]
Учитывая список L из п элементов со значениями или записями L 0 .... L п -1 , и целевым значением Т , следующие подпрограммы используют линейный поиск , чтобы найти индекс мишени T в L . [3]
Базовый алгоритм, приведенный выше, выполняет два сравнения за итерацию: одно для проверки, равно ли L i T , а другое для проверки, указывает ли я на действительный индекс списка. Добавив в список дополнительную запись L n ( контрольное значение ), которая равна цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет дозорного, если цель не содержится в списке. [4]
Если список упорядочен так, что L 0 ≤ L 1 ... ≤ L n -1 , поиск может быстрее установить отсутствие цели, завершив поиск, когда L i превышает цель. Этот вариант требует наличия более мощного дозорного, чем цель. [5]
Для списка с n элементами наилучший случай - это когда значение равно первому элементу списка, и в этом случае требуется только одно сравнение. В худшем случае значение отсутствует в списке (или встречается только один раз в конце списка), и в этом случае необходимо n сравнений.
Если искомое значение встречается в списке k раз и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно
Например, если искомое значение встречается в списке один раз и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно . Однако, если известно, что это происходит один раз, то требуется не более n - 1 сравнений, и ожидаемое число сравнений равно
(например, для n = 2 это 1, что соответствует единственной конструкции if-then-else).
В любом случае, асимптотически стоимость наихудшего случая и ожидаемая стоимость линейного поиска равны O ( n ).
Производительность линейного поиска улучшается, если желаемое значение с большей вероятностью находится в начале списка, чем в его конце. Следовательно, если одни значения будут найдены с большей вероятностью, чем другие, желательно поместить их в начало списка.
В частности, когда элементы списка расположены в порядке убывания вероятности и эти вероятности распределены геометрически , стоимость линейного поиска составляет всего O (1). [6]
Линейный поиск обычно очень прост в реализации и практичен, когда в списке всего несколько элементов или при выполнении одного поиска в неупорядоченном списке.
Когда в одном списке нужно искать много значений, часто имеет смысл предварительно обработать список, чтобы использовать более быстрый метод. Например, можно отсортировать список и использовать двоичный поиск или построить из него эффективную структуру данных поиска . Если содержимое списка часто меняется, повторная реорганизация может доставить больше хлопот, чем она того стоит.
В результате, хотя теоретически другие алгоритмы поиска могут быть быстрее, чем линейный поиск (например, двоичный поиск ), на практике даже на массивах среднего размера (около 100 элементов или меньше) может оказаться невозможным использовать что-либо еще. На больших массивах имеет смысл использовать другие, более быстрые методы поиска, только если данные достаточно большие, потому что начальное время для подготовки (сортировки) данных сравнимо со многими линейными поисками. [7]