Линейный поиск - Linear search

Линейный поиск
Учебный классАлгоритм поиска
Худший случай спектакльО(п)
Лучший случай спектакльО(1)
Средний спектакльО(п / 2)
Худший случай космическая сложностьО(1) итеративный

В Информатика, а линейный поиск или же последовательный поиск это метод поиска элемента в список. Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или пока не будет выполнен поиск по всему списку.[1]

В худшем случае - линейный поиск линейное время и делает самое большее п сравнения, где п длина списка. Если вероятность поиска каждого элемента одинакова, то линейный поиск имеет средний случай п + 1/2 сравнений, но средний случай может измениться, если вероятности поиска для каждого элемента различаются. Линейный поиск редко бывает практичным, потому что другие алгоритмы и схемы поиска, такие как алгоритм двоичного поиска и хеш-таблицы, позволяют значительно быстрее искать все, кроме коротких списков.[2]

Алгоритм

Линейный поиск последовательно проверяет каждый элемент списка, пока не найдет элемент, соответствующий целевому значению. Если алгоритм достигает конца списка, поиск завершается неудачно.[1]

Базовый алгоритм

Учитывая список L из п элементы со значениями или записи L0 .... Lп−1, и целевое значение Т, следующее подпрограмма использует линейный поиск, чтобы найти индекс цели Т в L.[3]

  1. Набор я до 0.
  2. Если Lя = Т, поиск завершается успешно; возвращаться я.
  3. Увеличивать я Автор: 1.
  4. Если я < п, перейдите к шагу 2. В противном случае поиск завершится неудачно.

С часовым

Базовый алгоритм, приведенный выше, выполняет два сравнения за итерацию: одно для проверки того, Lя равно Т, а другой, чтобы проверить, я по-прежнему указывает на действительный индекс списка. Добавив дополнительную запись Lп к списку (a контрольное значение ), равный цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет дозорного, если цель не содержится в списке.[4]

  1. Набор я до 0.
  2. Если Lя = Т, перейдите к шагу 4.
  3. Увеличивать я на 1 и перейти к шагу 2.
  4. Если я < п, поиск завершается успешно; возвращаться я. Иначе поиск завершается неудачно.

В упорядоченном столе

Если список упорядочен так, что L0 ≤ L1 ... ≤ Lп−1, поиск может быстрее установить отсутствие цели, завершив поиск один раз Lя превышает цель. Этот вариант требует, чтобы дозорный больше, чем цель.[5]

  1. Набор я до 0.
  2. Если Lя ≥ Т, перейдите к шагу 4.
  3. Увеличивать я на 1 и перейти к шагу 2.
  4. Если Lя = Т, поиск завершается успешно; возвращаться я. Иначе поиск завершается неудачно.


Анализ

Для списка с п items, в лучшем случае, когда значение равно первому элементу списка, и в этом случае требуется только одно сравнение. Худший случай - когда значение отсутствует в списке (или встречается только один раз в конце списка), и в этом случае п сравнения нужны.

Если искомое значение встречается k раз в списке, и все упорядочения списка равновероятны, ожидаемое количество сравнений

Например, если искомое значение встречается в списке один раз, и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений будет . Однако если это известен что это происходит один раз, то самое большее п - Требуется 1 сравнение, и ожидаемое количество сравнений равно

(например, для п = 2 это 1, что соответствует единственной конструкции if-then-else).

В любом случае, асимптотически стоимость наихудшего случая и ожидаемая стоимость линейного поиска равны О (п).

Неравномерные вероятности

Производительность линейного поиска улучшается, если желаемое значение с большей вероятностью находится в начале списка, чем в его конце. Следовательно, если одни значения будут найдены с большей вероятностью, чем другие, желательно поместить их в начало списка.

В частности, когда элементы списка расположены в порядке убывания вероятности, и эти вероятности геометрически распределенный, стоимость линейного поиска составляет всего O (1). [6]

Заявление

Линейный поиск обычно очень просто реализовать, и он практичен, когда в списке всего несколько элементов или при выполнении одного поиска в неупорядоченном списке.

Когда в одном списке нужно искать несколько значений, часто имеет смысл предварительно обработать список, чтобы использовать более быстрый метод. Например, можно Сортировать список и использование бинарный поиск, или создать эффективный структура данных поиска от него. Если содержимое списка часто меняется, повторная реорганизация может доставить больше хлопот, чем она того стоит.

В результате, даже если теоретически другие алгоритмы поиска могут быть быстрее линейного поиска (например, бинарный поиск ), на практике даже для массивов среднего размера (около 100 элементов или меньше) может оказаться невозможным использовать что-либо еще. На больших массивах имеет смысл использовать другие, более быстрые методы поиска, только если данные достаточно большие, потому что начальное время для подготовки (сортировки) данных сравнимо со многими линейными поисками.[7]

Смотрите также

Рекомендации

Цитаты

  1. ^ а б Кнут 1998, §6.1 («Последовательный поиск»).
  2. ^ Кнут 1998, §6.2 («Поиск по сравнению ключей»).
  3. ^ Кнут 1998, §6.1 («Последовательный поиск»), подраздел «Алгоритм B».
  4. ^ Кнут 1998, §6.1 («Последовательный поиск»), подраздел «Алгоритм Q».
  5. ^ Кнут 1998, §6.1 («Последовательный поиск»), подраздел «Алгоритм T».
  6. ^ Кнут, Дональд (1997). «Раздел 6.1: Последовательный поиск». Сортировка и поиск. Искусство программирования. 3 (3-е изд.). Эддисон-Уэсли. С. 396–408. ISBN  0-201-89685-0.
  7. ^ Хорват, Адам. «Производительность двоичного и линейного поиска на платформе .NET и Mono». Получено 19 апреля 2013.

Работает