Вопрос по arrays, algorithm, complexity-theory – Сколько сравнений сделает бинарный поиск в худшем случае, используя этот алгоритм?

17

Привет там ниже псевдокод для моей реализации двоичного поиска:

Input: (A[0...n-1], K)
begin
   l ← 0; r ← n-1
   while l ≤ r do
      m ← floor((l+r)/2)
      if K > A[m] then l ← m+1
      else if K < A[m] then r ← m-1 else return m
      end if 
   end while
   return -1 // key not found
end

Мне было просто интересно, как рассчитать количество сравнений, которые эта реализация сделает в худшем случае для отсортированного массива размером n?

Будет ли количество сравнений = lg n + 1? или что-то другое?

В вашем коде есть ошибка:if K > A[m] then return l ← m+1 должно бытьif K > A[m] then l ← m+1 безreturn. Gumbo

Ваш Ответ

3   ответа
16

если элемент K отсутствует в A и меньше всех элементов в A. Тогда у нас есть два сравнения на каждом шаге:K > A[m] а такжеK < A[m].

Ибо на каждом шаге массив разрезается на две части, каждая размером(n-1)/2у нас максимумlog_2(n-1) шаги.

Это приводит к общей2*log_2(n-1) сравнения, которые асимптотически действительно равныO(log(n)).

Худший случай должен быть, если все элементы одинаковы! Таким образом, временная сложность должна быть O (n)
5

бинарный поискНаихудшая производительность этого алгоритмаO(lg n), который измеряет асимптотическое число необходимых сравнений.actual количество сравнений в худшем случае будет2*lg(n-1), как было указано в ответе @ hielsnoppe.

Псевдокод в вопросе представляет типичную реализацию двоичного поиска, поэтому ожидаемые сложности производительности сохраняются для массива (или вектора) размераn:

Best case performance: O(1) Average case performance: O(lg n) Worst case performance: O(lg n)

При ближайшем рассмотрении в этом вопросе возникают две проблемы с псевдокодом:

The line: if K > A[m] then return l ← m+1 should read if K > A[m] then l ← m+1. You can't return yet The line: m ← floor((l+r)/2) might cause an overflow if the numbers are large enough when working with fixed-size integers. The correct syntax varies depending on the actual programming language you're using, but something along this will fix the problem: m ← (l + r) >>> 1, where >>> is the unsigned right shift operator. Read more about the problem in here.
10

ответ Хилснопе:

Вn-элементный массив (n > 0), элемент для сравнения находится в индексеm = floor((n-1)/2), Таким образом, есть три возможности

A[m] < K, then after one comparison, the search continues in an n-1-m = ceiling((n-1)/2)-element array. A[m] > K, then after two comparisons, the search continues in an m-element array. A[m] == K, then we're done after two comparisons.

Так что, если мы обозначим максимальное (наихудший) число сравнений для поиска вnмассив элементов поC(n), у нас есть

C(0) = 0
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0

Для странныхn = 2k+1пол и потолок идентичны, поэтому максимум, очевидно, последний,

C(2k+1) = 2 + C(k)

и дажеn = 2k, мы нашли

C(2k) = max { 1 + C(k), 2 + C(k-1) }.

Заn = 2, который разрешаетC(2) = 1 + C(1) = 1 + 2 = 3, для всего большего дажеnмаксимум2 + C(k-1), поскольку дляn >= 1 у нас естьC(n) <= C(n+1) <= C(n) + 1.

Оценка рекурсии для первых несколькихn, мы нашли

C(0) = 0
C(1) = 2
C(2) = 3
C(3) = C(4) = 4
C(5) = C(6) = 5
C(7) = C(8) = C(9) = C(10) = 6
C(11) = ... = C(14) = 7
C(15) = ... = C(22) = 8
C(23) = ... = C(30) = 9

Итак, по индукции мы докажем

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1)

или же

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))).

Это точная верхняя граница.

Похожие вопросы