時間計算量 の 二分探索 は O(log n) 、 どこ n 配列内の要素の数です。各ステップで配列を半分に分割します。 空間の複雑さ は ○(1) 一定量の追加スペースを使用するためです。

スイッチメソッドJava

二分探索アルゴリズムの例

二分探索アルゴリズムの時間と空間の複雑さについては、以下で説明します。

時間計算量 二分探索アルゴリズム :

二分探索アルゴリズムのベストケースの時間計算量: ○(1)

最良のケースは、要素が配列の中央のインデックスにある場合です。ターゲット要素を見つけるために必要な比較は 1 回だけです。したがって、最良のケースの複雑さは次のようになります。 ○(1) 。

二分探索アルゴリズムの平均ケース時間複雑さ: O(log N)

配列を考慮する 到着[] 長さの N と要素 バツ 見つけられる。次の 2 つのケースが考えられます。

• ケース1: 要素は配列内に存在します
• ケース2: 要素が配列内に存在しません。

がある N Case1と 1 事例２．したがって、ケースの合計数 = N+1 。ここで、次のことに注目してください。

文字列から整数への変換

• インデックス N/2 の要素は次の場所にあります。 1 比較
• インデックス N/4 および 3N/4 の要素は次の場所にあります。 2 比較。
• インデックス N/8、3N/8、5N/8、7N/8 の要素は次の場所にあります。 3 比較など。

これに基づいて、要素には次のものが必要であると結論付けることができます。

• 1 つの比較 = 1
• 2 つの比較 = 2
• 3 つの比較 = 4
• バツ 比較 = 2 ^x-1 どこ バツ 範囲に属します [1, logN] なぜなら、最大比較数 = 最大時間 N は、最初の要素 = logN に達するまでの最大比較数を半分にすることができるためです。

したがって、合計の比較
= 1*(1 回の比較を必要とする要素) + 2*(2 回の比較を必要とする要素) + 。 。 。 + logN*(logN の比較が必要な要素)
= 1*1 + 2*2 + 3*4 + 。 。 。 + logN * (2^ログN-1)
= 2^{落ち着いた}* (logN – 1) + 1
= N * (logN – 1) + 1

合計ケース数 = N+1 。

したがって、平均複雑さ = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) 。ここで、支配的な項は N*logN/(N+1) であり、これはおよそ 落ち着いた 。したがって、平均的なケースの複雑さは次のようになります。 O(logN)

二分探索アルゴリズムの最悪の場合の時間計算量: O(log N)

最悪のケースは、要素が最初の位置に存在する場合です。平均的なケースで見られるように、最初の要素に到達するために必要な比較は次のとおりです。 落ち着いた 。したがって、最悪の場合の時間計算量は次のようになります。 O(logN) 。

文字列を比較するJava

二分探索アルゴリズムの補助空間の複雑さ

の 補助空間の複雑さ の 二分探索アルゴリズム は ○(1) つまり、入力配列のサイズに関係なく、一定量の追加スペースが必要になります。これは、二分探索が反復アルゴリズムであり、追加のデータ構造や入力サイズとともに増大する再帰を必要としないためです。ただし、二分探索を再帰的に実装することもできます。