マインドマップギャラリー 第 1 章 はじめに
データ構造マインドマップ、データ構造の基本概念、アルゴリズム、アルゴリズム評価などに関する記事です。お役に立てれば!
2023-11-21 17:17:08 に編集されました第 1 章 はじめに
1.1 データ構造の基本概念
基本的な概念と用語
1. データ
コンピュータに入力し、コンピュータ プログラムによって認識および処理できるすべての記号のセット
コンピュータではすべてのデータはバイナリとして表現されます
2. データ要素
データ要素はデータの基本単位であり、通常は全体として考慮および処理されます。
3. データ項目
データ要素は、分割できないデータの最小単位である複数のデータ項目で構成されます。
4. データオブジェクト
データ オブジェクトは、同じプロパティを持つデータ要素のコレクションです。
5. データ型
データ型は、値のコレクションと、このコレクションに対して定義された一連の操作です。
分類
原子の種類
値が割り切れないデータ型
例: int
構造タイプ
値を細分化できるデータ型
例: 構造
抽象データ型 (ADT)
D: データオブジェクト
S: データ関係
P:基本操作
データ構造の 3 つの要素
1. データの論理構造
意味
相互に 1 つ以上の特定の関係を持つデータ要素のコレクション
分類
線状構造
一対一の関係
特徴
最初の要素を除き、他のすべての要素には「直接の先行要素」が 1 つだけあります。
最後の要素を除いて、他のすべての要素には一意の「直接後継要素」があります。
集める
同じセットに属している
木
1対多の関係
特徴
ルート ノードを除き、他のすべてのポイントには「直接の先行ノード」が 1 つだけあります。
葉ノードを除いて、他のすべての要素にはいくつかの「直接の後続要素」があります。
グリッド (グラフィック構造)
多対多の関係
特徴
どの頂点にも、複数の「直接の先行者」と「直接の後継者」が存在する可能性があります。
2. データの物理構造 (収納構造)
意味
ストレージ構造とは、コンピュータ内のデータ構造の表現 (イメージとも呼ばれます) を指し、物理構造とも呼ばれます。
分類
シーケンシャルストレージ構造
意味
論理的に隣接するノードを物理的に隣接するストレージ ユニットに格納します。
通常は配列で表現される
アドバンテージ
ランダムアクセスが実現できる
各要素が占めるスペースは最小です
欠点がある
ストレージスペースの隣接するブロック全体のみを使用できるため、断片化が起こりやすくなります。
図
チェーンストレージ構造
意味
論理的に隣接する要素が物理的にも隣接している必要はありません。
ポインタを使用して要素間の論理関係を表す
アドバンテージ
すべての収納スペースを最大限に活用する
欠点がある
シーケンシャルアクセスのみ
ポインタは追加の記憶領域を占有します
説明する
ノード内のストレージユニットアドレス: 連続している必要があります
ノード間のストレージユニットのアドレス: 連続している必要はありません
図
インデックスの格納構造
意味
データ要素情報を格納する際に、インデックス テーブルも作成されます。
一般的な形式は次のとおりです: <キーワード、アドレス>
アドバンテージ
高速検索
欠点がある
インデックステーブルは追加のストレージスペースを占有します
データを追加または削除する場合は、インデックス テーブルを変更する必要があります
ハッシュストレージ構造
意味
キーワードのサイズに基づいてデータ要素のアドレスを直接計算します。
ハッシュストレージとも呼ばれます
アドバンテージ
ノードの取得、追加、削除が高速です
欠点がある
ハッシュ関数が適切でない場合、ストレージの競合が発生し、競合を解決するために時間とスペースのオーバーヘッドが増加します。
非順次ストレージ構造
3. データ操作
意味
データに適用される操作には、操作の定義と実装が含まれます。
操作は論理構造に対して定義されます
操作の実装は物理構造に基づいています
1.2 アルゴリズムとアルゴリズムの評価
アルゴリズムの基本概念
価値のある式 = データ構造 アルゴリズム = プログラム
1. アルゴリズムの定義
これは、特定の問題を解決するための手順の説明であり、各命令が 1 つ以上の操作を表す有限の命令シーケンスです。
2. アルゴリズムの記述方法
自然言語
フローチャート
疑似コード
プログラミング言語
3. アルゴリズムの5つの特徴
(1) 有限性
有限ステップの実行後に終了し、各ステップは有限時間内に完了できます
例: 無限ループプログラムコード
(2) 確実性
読者が理解する際に曖昧さがないよう、各指示には正確な意味がなければなりません。
同じ入力に対しては同じ出力しか得られない
(3) 実現可能性
アルゴリズムで記述された演算は、基本演算を限られた回数実行することで実現できます。
(4)入力
アルゴリズムには 0 個以上の入力があります
(5)出力
アルゴリズムには 1 つ以上の出力があります
4. アルゴリズムの評価
(1) 正しさ
アルゴリズムが問題を正しく解決する
「正しい」レベル
a. プログラムに文法上の誤りはありません。
b. 複数のメソッド入力データのセットについて、要件を満たす出力結果を生成できます。
c. 不正な入力データの要件を満たす出力結果を生成できること。
d. すべての合法的な入力データについて、要件を満たす出力結果を生成できます。
(2) 可読性
人々がアルゴリズムを理解できるようにする
(3) 堅牢性
入力データが不正な場合でも、アルゴリズムは適切に反応または処理できます。
(4) 高効率かつ低ストレージ要件
効率とは、アルゴリズムの実行にかかる時間を指します。
ストレージ要件とは、アルゴリズムの実行中に必要な最大ストレージ容量を指します。
アルゴリズムのメトリクス
メトリクス
時間の複雑さ
空間の複雑さ
測定方法
イベント後の統計
コンピューターのタイマーを使用して、コンピューター上のプログラムの実行時間を計測する
欠点がある
(1) アルゴリズムに基づいてコンパイルされたプログラムを最初に実行する必要があります
(2) 実行時間は、コンピュータのハードウェアやソフトウェアなどの環境要因によって異なります。
(3) プログラムの実行コストが比較的高い
事前分析と推定
コンピュータープログラミングの前に、アルゴリズムは統計的手法に基づいて推定されます
実行にかかる時間は以下によって異なります
(1) アルゴリズムはどのような戦略を選択する必要がありますか?
(2) 問題の規模
(3) プログラムを書くための言語
(4) コンパイルによって生成される機械語コードの品質
(5) マシンが命令を実行する速度
フォーカスポイント
コンピューターのハードウェアとソフトウェアに関連する要因はさておき、特定のアルゴリズムの「実行中のワークロード」のサイズは問題のサイズ (n) にのみ依存すると考えることができます。つまり、それは問題の関数です。問題の大きさ。
時間の複雑さ
計算方法
文章の頻度
最も深いループ内のステートメントで元の操作が実行された回数
関数表現
一般に、アルゴリズムの基本操作が繰り返される回数は問題サイズ n の関数 f(n) であり、アルゴリズムの時間測定は T(n)=O(f(n)) として記録されます。 (時間計算量)
フォーカスポイント
最高レベルだけを見る
定数項を削除する
係数を無視する
一般的な O(n) サイズの関係
3つの条件
最高の時間計算量
最悪の時間複雑さ
平均時間計算量
影響を与える要因
データの初期状態
問題のサイズ
空間の複雑さ
計算方法
アルゴリズムの空間複雑度は、S(n)=O(f(n)) として記録されます。
フォーカスポイント
入力とプログラムを超えた余分なスペースを分析