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

У меня есть отсортированный список элементов:

c f g o p q r t w

Мне нужно найти элемент f с помощью бинарного поиска, я это сделал. Я также нашел этот элемент, используя линейный поиск в 2 сравнениях. Теперь мне нужно показать, что в этом случае линейный код быстрее бинарного, как мне это сделать? Благодарю вас!


algorithm binary-search linear-search
person Ganz    schedule 25.09.2014    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Подсчитайте операции, требуемые каждым алгоритмом. Грубо говоря, для бинарного поиска требуется:

  • Вычислить среднюю точку = 5
  • Сравните «п» с «ф»
  • Вычислить среднюю точку = 3
  • Сравните «г» с «ф»
  • Вычислить среднюю точку = 2
  • Сравните «f» с «f» — успех

примерно на 6 операций.

Линейный поиск, с другой стороны, требует только:

  • Сравните «с» с «f»
  • Сравните «f» с «f» — успех

Линейный поиск еще быстрее, если вы считаете необходимым включить индексные вычисления для перебора списка:

  • i=1
  • Сравните «с» с «f»
  • i=2
  • Сравните «f» с «f» — успех
person chepner    schedule 25.09.2014

arrow_upward
0
arrow_downward

Выполните оба случая и подсчитайте количество операций в каждом. Двоичный поиск будет больше.

person MasterID    schedule 25.09.2014

arrow_upward
0
arrow_downward

Ниже я предполагаю, что искомый элемент существует в массиве. Двоичный поиск занимает log2(N) итераций, чтобы найти нужный элемент в худшем случае. Средний случай близок к этому. Линейный поиск занимает в среднем N/2 итераций, чтобы найти элемент.

Итерация бинарного поиска обычно состоит из 3-4 шагов: вычисление среднего индекса, выбор среднего элемента и до двух сравнений. Таким образом, в среднем поиск с использованием бинарного поиска займет log2(N) * 3,5 шага.

В линейном поиске требуется две операции — получение значения элемента по текущему индексу и сравнение. В среднем линейный поиск займет N * 2/2 = N шагов.

В вашем случае у нас есть log2(9) * 3,5 = 3,1 * 3,5 = 10,85 шагов для бинарного поиска. И 9 шагов для линейного поиска.

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

person Aivean    schedule 25.09.2014