データ構造における検索方法の比較

場合によっては、いくつかのキーを見つけるためにさまざまな検索スキームを実行します。このセクションでは、シーケンシャル検索とバイナリ検索の2つの検索手法の基本的な違いを説明します。

シーケンシャル検索	二分探索
時間計算量はO（n）	時間計算量はO（log n）
一定時間内に最初の位置に存在するキーを検索します	一定時間内に中央位置に存在するキーを検索します
コンテナ内の要素のシーケンスは影響しません。	要素はコンテナ内で並べ替える必要があります
配列とリンクリストを使用してこれを実装できます	リンクリストに直接実装することはできません。これを実装するには、リストの基本的なルールを変更する必要があります
アルゴリズムは本質的に反復的です	アルゴリズム手法は分割統治法です。
アルゴリズムは実装が簡単で、必要なコードの量も少なくて済みます。	アルゴリズムは少し複雑です。実装にはより多くのコードが必要です。
最悪の場合、N回の比較が必要です。	最悪の場合、ログn回の比較で十分です。

データ構造の並べ替え方法の比較

データ構造におけるスタックADT

データ構造の二分探索木
二分探索木は、いくつかの特性を持つ二分木です。これらのプロパティは次のようなものです- すべての二分探索木は二分木です左の子はすべて、ルートよりも価値が低くなりますすべての正しい子はrootよりも大きな価値を持ちます理想的な二分探索木は、同じ値を2回保持することはありません。このようなツリーが1つあるとします- このツリーは1つの二分探索木です。上記のすべてのプロパティに従います。要素をインオーダートラバーサルモードにトラバースすると、5、8、10、15、16、20、23を取得できます。これをC++コードで実装する方法を理解するために1つのコードを見てみましょう。例 #
データ構造の償却時間計算量
償却分析この分析は、時折の操作が非常に遅い場合に使用されますが、非常に頻繁に実行される操作のほとんどは高速です。データ構造では、ハッシュテーブル、互いに素なセットなどの償却分析が必要です。ハッシュテーブルでは、ほとんどの場合、検索時間の複雑さはO（1）ですが、O（n）操作を実行することもあります。ほとんどの場合、ハッシュテーブルで要素を検索または挿入する場合、タスクは一定時間かかりますが、衝突が発生すると、衝突を解決するためにO（n）回の操作が必要になります。集計方法総コストを見つけるために集計方法が使用されます。大量のデータを追加する場合は、この式で償却原価を見つける必要があり