 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
| Учебный класс | Алгоритм поиска |
|---|---|
| Пессимистический производительность | О ( п ) |
| Лучшая производительность | О (1) |
| Средняя производительность | O ( п / 2 ) |
| Сложность пространства в наихудшем случае | O (1) итеративный |
В информатике , линейный поиск или последовательный поиск представляет собой метод для нахождения элемента в списке . Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или пока не будет выполнен поиск по всему списку. [1]
Линейный поиск выполняется в худшем случае за линейное время и выполняет не более n сравнений, где n - длина списка. Если вероятность поиска каждого элемента одинакова, то линейный поиск имеет средний случайп + 1/2сравнений, но средний случай может измениться, если вероятности поиска для каждого элемента различаются. Линейный поиск редко бывает практичным, потому что другие алгоритмы и схемы поиска, такие как алгоритм двоичного поиска и хэш-таблицы , позволяют значительно быстрее искать все, кроме коротких списков. [2]
Алгоритм [ править ]
Линейный поиск последовательно проверяет каждый элемент списка, пока не найдет элемент, соответствующий целевому значению. Если алгоритм достигает конца списка, поиск завершается неудачно. [1]
Базовый алгоритм [ править ]
Учитывая список L из п элементов со значениями или записями L 0 .... L п -1 , и целевым значением Т , следующие подпрограммы используют линейный поиск , чтобы найти индекс мишени T в L . [3]
- Установите i в 0.
- Если L i = T , поиск завершается успешно; вернуться я .
- Увеличьте i на 1.
- Если i < n , перейти к шагу 2. В противном случае поиск завершится неудачно.
Со стражем [ править ]
Базовый алгоритм, приведенный выше, выполняет два сравнения за итерацию: одно для проверки, равно ли L i T , а другое для проверки, указывает ли я на действительный индекс списка. Добавив в список дополнительную запись L n ( контрольное значение ), которая равна цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет дозорного, если цель не содержится в списке. [4]
- Установите i в 0.
- Если L i = T , перейдите к шагу 4.
- Увеличьте i на 1 и перейдите к шагу 2.
- Если i < n , поиск завершается успешно; вернуться я . Иначе поиск завершается неудачно.
В упорядоченной таблице [ править ]
Если список упорядочен так, что L 0 ≤ L 1 ... ≤ L n -1 , поиск может быстрее установить отсутствие цели, завершив поиск, когда L i превышает цель. Этот вариант требует, чтобы дозорный больше, чем цель. [5]
- Установите i в 0.
- Если L i ≥ T , перейдите к шагу 4.
- Увеличьте i на 1 и перейдите к шагу 2.
- Если L i = T , поиск завершается успешно; вернуться я . Иначе поиск завершается неудачно.
Анализ [ править ]
Для списка из n элементов наилучший случай - это когда значение равно первому элементу списка, и в этом случае требуется только одно сравнение. Худший случай - когда значение отсутствует в списке (или встречается только один раз в конце списка), и в этом случае необходимо n сравнений.
Если искомое значение встречается в списке k раз и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно
![{\ begin {case} n & {\ mbox {if}} k = 0 \\ [5pt] \ displaystyle {\ frac {n + 1} {k + 1}} & {\ mbox {if}} 1 \ leq k \ leq n. \ end {case}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c31d35edb255baee3eeb7111ce8a1f7d44a3878)
Например, если искомое значение встречается в списке один раз, и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно . Однако, если известно, что это происходит один раз, то требуется не более n - 1 сравнений, и ожидаемое количество сравнений равно
(например, для n = 2 это 1, что соответствует единственной конструкции if-then-else).
В любом случае, асимптотически стоимость наихудшего случая и ожидаемая стоимость линейного поиска равны O ( n ).
Неоднородные вероятности [ править ]
Производительность линейного поиска улучшается, если желаемое значение с большей вероятностью находится в начале списка, чем в его конце. Следовательно, если одни значения будут найдены с большей вероятностью, чем другие, желательно поместить их в начало списка.
В частности, когда элементы списка расположены в порядке убывания вероятности и эти вероятности распределены геометрически , стоимость линейного поиска составляет всего O (1). [6]
Заявление [ править ]
Линейный поиск обычно очень прост в реализации и практичен, когда в списке всего несколько элементов или при выполнении одного поиска в неупорядоченном списке.
Когда в одном списке нужно искать несколько значений, часто имеет смысл предварительно обработать список, чтобы использовать более быстрый метод. Например, можно отсортировать список и использовать двоичный поиск или построить из него эффективную структуру данных поиска . Если содержимое списка часто меняется, повторная реорганизация может доставить больше хлопот, чем она того стоит.
В результате, хотя теоретически другие алгоритмы поиска могут быть быстрее линейного поиска (например, двоичный поиск ), на практике даже на массивах среднего размера (около 100 элементов или меньше) может оказаться невозможным использовать что-либо еще. На больших массивах имеет смысл использовать другие, более быстрые методы поиска, только если данные достаточно большие, потому что начальное время для подготовки (сортировки) данных сопоставимо со многими линейными поисками. [7]
См. Также [ править ]
- Тернарный поиск
- Хеш-таблица
- Задача линейного поиска
Ссылки [ править ]
Цитаты [ править ]
- ^ a b Knuth 1998 , §6.1 («Последовательный поиск»).
- ^ Knuth 1998 , §6.2 («Поиск путем сравнения ключей»).
- ^ Knuth 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм B».
- ^ Knuth 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм Q».
- ^ Knuth 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм T».
- ^ Кнут, Дональд (1997). «Раздел 6.1: Последовательный поиск». Сортировка и поиск . Искусство программирования. 3 (3-е изд.). Эддисон-Уэсли. С. 396–408. ISBN 0-201-89685-0.
- ^ Хорват, Адам. «Производительность двоичного и линейного поиска на платформе .NET и Mono» . Проверено 19 апреля 2013 года .
Работает [ править ]
- Кнут, Дональд (1998). Сортировка и поиск . Искусство программирования . 3 (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли Профессионал.CS1 maint: ref=harv (link) ISBN 0-201-89685-0
