二分探索
バイナリ・ルックアップは、要素の順序付きリストを入力とするアルゴリズムです。検索対象の要素がリストに含まれていれば、バイナリ・ルックアップはその位置を返し、含まれていなければNULLを返します。
- バイナリ検索は、単純な検索よりもはるかに高速です。
- O(log n)の方がO(n)よりも高速です。検索が必要な要素が多ければ多いほど、前者は後者よりも高速です。
- アルゴリズム実行イベントの計測単位は秒ではありません。
- アルゴリズムの実行イベントは、その成長率で測定されます。
- アルゴリズムの実行時間はO
選択ソート
メモリの仕組み
例えば、ショーに行く前にロッカーに何かを入れなければならないとして、ロッカーにはたくさんの引き出しがあり、その中から2つの引き出しを選んで荷物を入れると、ショーに行くのが楽しくなります。このプロセスは、コンピュータのメモリーの仕組みとほぼ同じです。andはたくさんの引き出しの集合体のようなものですが、それぞれの引き出しにはアドレスがあります。データを格納する基本的な方法には、配列とリンクリストの2つがあります。
配列と連鎖表
アレイは、あなたが映画館に行って友人と一緒に座り、一緒に同じ住所にいるのと同じです。その結果、別の友人がやってきて、あなたの隣の席はすでに取られており、あなたは全員一緒に座るために、全員が座れる新しい席に変更します。
連鎖表は借り物競走のようなもので、通過するレベルごとに次のレベルを指すアドレスが示されます。つまり、連鎖表と配列の違いは、配列のすべての要素が同じメモリアドレスに一緒に格納されていなければならないのに対して、連鎖表はそうではないということです。例えば、あなたと50人の友達がインターネットに行ったとします。しかし、マシンをつなげるのではなく、別々に座らなければなりません。これは配列ではできないケースで、連鎖リストならできます。
配列とリンクリストの違い
連鎖したテーブルの最後の要素にアクセスする場合、2番目の要素のアドレスは、最初の要素を経由して、最後の要素のアドレスを見つけることによってのみ見つけることができます。このため、要素の読み取りは非常に非効率的です。一方、配列ではすべての要素に同時にアクセスできるので、どの要素のアドレスにアクセスしてもはるかに効率的です。
まとめ
- コンピュータのメモリは、引き出しの山のようなものです。
- 複数の要素を格納する必要がある場合は、配列またはリンクリストを使用します。
- 配列の要素はすべて一緒です。
- リンクされたテーブルの要素は分離され、各要素には次の要素のアドレスが格納されます。
- 配列は読み込みが速い
- 連鎖したテーブルの挿入と削除が高速
- 同じ配列の要素はすべて同じ型でなければなりません。
