トップ > アルゴリズムとデータ構造

アルゴリズムとデータ構造

アルゴリズムとデータ構造について本を3時間くらいかけてバーって読んだので後から思い出すようのメモ程度のまとめ．

1章

  • アルゴリズム
  • 時間計算量
    • 最良時間計算量
    • 最悪時間計算量
    • オーダ記法

2章 データ構造

基本的構造

  • 配列
  • 連結リスト

大量のデータに対応

配列

  • 番号の指定で任意の場所に読み出しや格納可能
  • データの追加や削除：O(n)かかってしまう…データの有無の確認が必要なため
  • 配列サイズの事前決定が必要

連結リスト

  • 各レコードをポインタで指す
  • 格納するデータのサイズに応じて格納場所を変更出来る
  • 先頭データの追加削除がO(1)で出来る．
  • 探索に時間かかる
  • 同サイズの配列の2倍の記憶領域必要

スタック

  • FILO,LIFO
  • pushとpop：O(1)

キュー

3章 基本概念

  • 木

完全二分木は配列を用いて表すことが出来る．

再帰アルゴリズム

4章 データの探索

  • 探索
  • 二分探索：O(log n)
  • ハッシュ法：O(1)

5章 ソート1

  • ソート
  • 選択ソート：O(n2)…最大を見つける．
  • 挿入ソート：O(n)~O(n2)
  • ヒープソート：O(n log n)…ヒープの利用．ヒープ木．

ヒープ

スタックやキューと同様に，大量のデータを特定の順序で記憶するためのデータ構造．優先順位付きの処理を実現する．

値の大きいデータを優先順位が高いものとして，先に取り出せるようにしたデータ構造．

  • push_heap：O(log n)…葉の部分に追加，親と比較して交換，を繰り返す．
  • delete_maximum…根を取り出し，右端の葉を根に格納．子と比較して大きい方と交換，を繰り返す．

6章 ソート2 :クイックソート

一般的に最も高速に動作するとされるソートアルゴリズム．

  • 基準値による分割処理の繰り返しによってソートを行う
  • partition:基準値の決定，その基準値で分割．という処理：O(n)
  • 時間計算量：O(n log n)
  • 安定なソート：：同スコアなものは元の順序を適用出来るソート，選択ソート，挿入ソート

7章 アルゴリズムの設計手法1 分割統治法

  • 分割統治法
    1. 分割
    2. 統治
    3. 組合せ
  • 分割統治法は再帰の使用が一般的．
  • 分割統治法代表例：マージソート

大きな整数かけ算のアルゴリズム．64bit変数では19桁以下の整数しか扱えない．

8章 アルゴリズムの設計手法2

  • グリーディ法…全体を考慮せず各場面の最善らしい選択を行う．問題に対して適不適．
  • 動的計画法…問題の分割，同じ部分が出現に備え部分問題の解の記録．再計算の時間節約．
  • ナップサック問題…グリーディ法：O(nlogn),動的計画法：O(cn)

9章 アルゴリズムの設計手法3

  • バックトラック法…解の列挙が必要な問題に対して．列挙木
  • 分岐限定法…バックトラック法に加えて用いられる．枝刈り．

10章 グラフアルゴリズム

  • グラフ…頂点，辺，経路
  • 隣接行列：2次元配列，隣接リスト：各頂点に対する連結リスト．
  • グラフの探索
  • 幅優先探索
  • 深さ優先探索
  • 最短経路問題…ダイクストラ法：グリーディ法に基づく．

11章 多項式と行列

12章 文字列照合アルゴリズム

  • 文字列照合…n文字のテキストからm文字のパターンを探す．
  • 基本アルゴリズム:O(n)~O(mn)
  • ホールスプールのアルゴリズム…パターン照合をパターンの右から行って不一致のときは不一致のテキストの右端の文字を利用して次に飛ぶ．
  • ホイヤームーア法…“照合をパターンの右から行い不一致の文字の情報を利用”&“照合で一致した部分の情報を利用”

13章 アルゴリズムの限界

  • 問題を解く最も高速なアルゴリズムの最悪時間計算量 = 問題の複雑さ．同じ複雑さの問題の集合 = 問題のクラス．クラス階層
  • 時間計算量が入力サイズの多項式で表される問題のクラス = クラスP．問題の解の検証を多項式時間で出来る問題のクラス = クラスNP
  • 非可解な問題．
参考文献

読んだ本．まぁなんとなく全体的に理解した．理論はサラッとでいいのでpythonによる実装をちょっとやっていきたい．