線形検索とバイナリ検索
コンテンツ
線形検索とバイナリ検索の違いは、線形検索では各要素がチェックおよび比較されてからソートされるのに対し、バイナリ検索ではソートされるリストは2つの部分に分割されてからソートされるということです。検索と並べ替えは、コンピュータープログラミングの2つの主要な概念です。検索と並べ替えには多くのアルゴリズムが使用されますが、検索と並べ替えに最もよく使用される2つのアルゴリズムは、線形検索とバイナリ検索です。
線形検索とバイナリ検索の違いは、両方のアルゴリズムの機能と効率です。バイナリ検索は、線形検索アルゴリズムに比べてはるかに効率的なアルゴリズムです。反復またはソートの前に各値を比較するのにかかる時間は、線形検索に比べてバイナリ検索の方が短くなります。
リスト内の数値を検索し、リスト内の値の数を比較および反復したい場合、線形検索は非常に複雑なアルゴリズムです。リストの各要素が1つずつ取得され、隣接する要素と比較されます。すべての要素にアクセスしてチェックすると、正しい要素が見つかります。リストの最後の番号が検索対象の番号である場合、最悪の場合があります。線形検索は、配列をトラバースし、検索する要素を見つける方法です。効率について説明する場合、効率とは、その数を見つけるためにプログラムを実行する必要がある回数です。最初の位置で探している数値が見つかった場合、比較は1回だけ行う必要があり、物事はソートされますが、そうでない場合は比較を何度も行う必要があり、メモリが無駄になります。平均して、比較の数は(n + 1/2)になります。また、この手法の最悪の場合の効率はO(n)が実行順序を表します。
線形検索と比較して、バイナリ検索は非常に効率的です。この方法では、配列は2つの部分に分割され、この方法で比較の数はバイナリ検索と比較して非常に少なくなります。また、バイナリ検索では、線形検索に比べて時間が短縮されます。バイナリ検索は、配列の中央の要素を見つけて、中央の要素を配列の一部と比較する方法で機能します。中間番号は、検索する必要のある番号、中間番号より小さい番号、または中間番号の中間より大きい番号の3つの可能性があります。比較の数は最大でlog(N + 1)です。線形検索と比較したバイナリ検索は、線形検索と比較すると効率的なアルゴリズムですが、バイナリ検索を実行する前に配列を並べ替える必要があります。
内容:線形検索とバイナリ検索の違い
- 比較表
- バイナリ検索
- 主な違い
- 結論
- 説明ビデオ
比較表
基礎 | 線形検索 | バイナリ検索 |
意味 | 各要素をチェックして比較し、並べ替える線形検索 | ソートされるリストのバイナリ検索は、2つの部分に分割されてからソートされます。
|
時間の複雑さ | 線形検索の時間の複雑さはO(N)です。 | バイナリ検索の時間の複雑さはO(log 2 N) |
アルゴリズムの種類 | 線形検索は反復的です。 | バイナリ検索は、分割統治です。 |
コードの行 | 線形検索では、さらにコードを記述する必要があります。 | バイナリ検索では、より少ないコードを記述する必要があります。 |
線形検索
リスト内の数値を検索し、リスト内の値の数を数回比較および反復する場合、線形検索は非常に複雑なアルゴリズムです。リストの各要素が1つずつ取得され、隣接する要素と比較されます。すべての要素にアクセスして確認すると、正しい要素が見つかります。リストの最後の番号が検索対象の番号である場合、最悪の場合があります。線形検索は、配列をトラバースし、検索する要素を見つける方法です。効率について説明する場合、効率とは、その数を見つけるためにプログラムを実行する必要がある回数です。最初の位置で探している数値が見つかった場合、比較は1回だけ行う必要があり、物事はソートされますが、そうでない場合は比較を何度も行う必要があり、メモリが無駄になります。平均して、比較の数は(n + 1/2)になります。そして、この手法の最悪の場合の効率はO(n)が実行の順序を表すことです。
バイナリ検索
線形検索と比較して、バイナリ検索は非常に効率的です。この方法では、配列が2つの部分に分割され、この方法で比較の数がバイナリ検索と比較して非常に少なくなります。また、バイナリ検索では、線形検索に比べて時間が短縮されます。バイナリ検索は、配列の中央の要素を見つけて、中央の要素を配列の一部と比較する方法で機能します。
中間番号は、検索する必要のある番号、中間番号より小さい番号、または中間番号の中間より大きい番号の3つの可能性があります。比較の数は最大でlog(N + 1)です。線形検索と比較したバイナリ検索は、線形検索と比較すると効率的なアルゴリズムですが、バイナリ検索を実行する前に配列を並べ替える必要があります。
主な違い
- 線形検索では各要素がチェックされ、比較されてから並べ替えられますが、バイナリ検索では並べ替えられるリストは2つの部分に分割されてから並べ替えられます。
- 線形検索の時間計算量は0(N)ですが、バイナリ検索の時間計算量はO(log2N)。
- 線形検索は反復的ですが、バイナリ検索は分割統治です。
- 線形検索では、より多くのコードを記述する必要がありますが、バイナリ検索では、より少ないコードを記述する必要があります。
結論
上記のこの記事では、線形検索とバイナリ検索の明確な違いがわかります。