20

こんにちは、以下は私の二分探索実装の疑似コードです。

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 でしょうか? または何か違う？

4

3 に答える 3

20

この場合の最悪のケースは、要素 K が A に存在せず、A のすべての要素よりも小さい場合です。その場合、各ステップで と の 2 つの比較がK > A[m]ありK < A[m]ます。

各ステップでは、配列がそれぞれのサイズの 2 つの部分に分割されて(n-1)/2いるため、最大log_2(n-1)ステップ数があります。

これにより、2*log_2(n-1)比較の合計が得られ、漸近的に実際に に等しくなりO(log(n))ます。

于 2012-05-13T11:23:19.193 に答える
12

hielsnoppeの答えに対する非常に小さな修正：

n要素配列 ( ) では、n > 0比較する要素は index にありますm = floor((n-1)/2)。ということで、可能性は3つ

  1. A[m] < Kの場合、1 回の比較の後、n-1-m = ceiling((n-1)/2)要素配列で検索が続行されます。
  2. A[m] > Kの場合、2 回の比較の後、m要素配列内で検索が続行されます。
  3. A[m] == Kの場合、2 回の比較を行って完了です。

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 >= 1C(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)))).

これは正確な上限です。

于 2012-05-13T13:25:37.600 に答える
6

二分探索に関するウィキペディアのページによると、このアルゴリズムの最悪の場合のパフォーマンスはでありO(lg n)、これは必要な比較の無症候性の数を測定します。@hielsnoppeの回答で指摘されているように、実際の最悪の場合の比較数はです。2*lg(n-1)

問題の擬似コードは、バイナリ検索の一般的な実装を表しているため、予想されるパフォーマンスの複雑さは、サイズの配列（またはベクトル）にも当てはまりますn。

  • 最高のパフォーマンス： O(1)
  • 平均的なケースのパフォーマンス：O(lg n)
  • 最悪の場合のパフォーマンス： O(lg n)

よく調べてみると、質問の擬似コードには2つの問題があります。

  • 行：if K > A[m] then return l ← m+1は読む必要がありますif K > A[m] then l ← m+1。まだ戻れない
  • 行：m ← floor((l+r)/2)固定サイズの整数を処理するときに数値が十分に大きい場合、オーバーフローが発生する可能性があります。正しい構文は、使用している実際のプログラミング言語によって異なりますが、これに沿った何かが問題を修正します。m ← (l + r) >>> 1ここ>>>で、は符号なし右シフト演算子です。ここで問題の詳細をお読みください。
于 2012-05-13T11:11:21.303 に答える