プログラミング作法 第2章 アルゴリズムとデータ構造を読んだ

探索

• データ量が少ない時は逐次探索・線形探索で十分高速
• 大きめの配列では二分探索を使う
  • 真ん中の要素を調べ、探している値より大きかったら前半、小さかったら後半を調べて、見つかるか存在しないと分かるまで探索する
  • この方法を使うには配列がソートされており、配列の長さがわかっている必要がある
  • ステップ数はlog2n(nを2で除算できる回数)

ソーティング

• クイックソート
  • ピボットの要素をとり、それより大きいグループと小さいグループに分ける処理を再起的に行うことでソートする
  • 挿入法やバブルソートと比較して桁違いに高速
  • 動作が入力データに依存するアルゴリズムもある

O記法

• 計算量はnの関数として表現される
• 最悪なケースと期待される動作は区別する

リスト

• 配列との違いはサイズとソートの容易さ
  • 配列は決まったサイズになるが、リストは中身を記憶するサイズ＋ポインタを記憶するサイズ
  • リストはポインタを交換することで順序を変更できるが、配列はブロック移動作業のコストが高い
    • リストの末尾に要素を追加する作業は通常O(n)になるが、別途末尾のポインタを管理する等の対応でO(1)にすることもできる

ツリー

• リストや配列ではO(n)かかる処理も、ツリーならO(logn)で済むようになる
• バランス木
  • ルートからリーフまでの個々の経路がほぼ同じ長さのツリー
  • 項目を検索する作業がO(logn)で済む

ハッシュテーブル

• 配列とリストと数学的処理を組み合わせ、効率よく動的データを記憶し取得できるデータ構造
• 応用例として、キーに対して何らかの値を関連づけるシンボルテーブルがある
• キーをハッシュ関数に渡してハッシュ値を生成し、情報が記憶されているテーブルのインデックスとして使用
• ハッシュテーブルはリストの配列
  • ハッシュ値を共有する項目同士をチェインするリストが入る
• シンボルテーブルにハッシュ値を記憶しておく