二分探索アルゴリズムを使用したプログラムの時間計算量はどれくらいですか?

二分探索アルゴリズムを使用したプログラムの時間計算量は「対数レベル」です。二分探索は効率の高い探索手法であり、アルゴリズムの複雑さはwhileループの回数であり、時間計算量は「O(h)=O(log2n)」で表されます。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

二分探索アルゴリズムを使用したプログラムの時間計算量は「対数レベル」です。

関連おすすめ:「プログラミング学習」

二分探索は二分探索(Binary Search)とも呼ばれ、より効率的な探索方法です。ただし、二分探索では、線形テーブルが逐次記憶構造を採用し、テーブル内の要素がキーワード順に配置されている必要があります。

検索処理:

まず、表内の要素が昇順に並んでいると仮定して、表の中央に記録されているキーワードと検索キーワードを比較します。等しい場合、検索は成功します。そうでない場合は、中央の位置のレコードを使用してテーブルを前後のサブテーブルに分割します。中央の位置に記録されたキーワードが検索キーワードより大きい場合、前のサブテーブルがさらに検索され、それ以外の場合は後者のサブテーブルがさらに検索されます。条件を満たすレコードが見つかって検索が成功するまで、またはサブテーブルが存在しない場合は検索が失敗するまで、上記のプロセスを繰り返します。

アルゴリズムの複雑さ:

二分探索の基本的な考え方は、n 個の要素をほぼ等しい 2 つの部分に分割し、a[n/2] を x と比較することです。 、x=a[n/2] の場合、x が見つかりアルゴリズムは終了します。xa の場合)。 [n/2] の場合は、配列 a の右半分で x を検索します。

時間計算量は while ループの数です。

合計 n 個の要素があり、

は n、n/2、n/4、....n/2^k と徐々に続きます (残りの要素数は次に操作されます) )、ここで、k はループの数です。

n/2^k>=1

を四捨五入すると、n/2^k=1

が得られます。 k=log2n、(基数 2、n の対数に基づく)

したがって、時間計算量は O(h)=O(log2n)

として表すことができます。二分探索を実装するための疑似コードを以下のように提供します:

BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max

半探索法は二分探索法とも呼ばれ、要素間の順序関係を利用し、分割法を採用します。 and-conquer 戦略: 最悪の場合、O (log n) で検索タスクが完了します。その基本的な考え方は次のとおりです: (配列要素が昇順に配置されていると仮定して) n 個の要素をほぼ同じ数で 2 つの半分に分割し、a[n/2] を取得し、それを探したい x と比較します (x= の場合)。 a[n/ 2] の場合、x が見つかり、アルゴリズムは終了します。x

さらに関連記事を読みたい場合は、PHP 中国語 Web サイト にアクセスしてください。 ！

以上が二分探索アルゴリズムを使用したプログラムの時間計算量はどれくらいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。