ホーム » スタッフ » 斉藤徹 » データ構造とアルゴリズムの総括

2010年1月
« 12月   2月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

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

処理速度・メモリの使用量・プログラミングの容易さのトレードオフの理解という点で、 まとめる。

  • 単純配列
    • 検索処理O(N),挿入処理O(N)
    • 固定サイズで最大量不定ならメモリ使用効率×、巨大一定
    • 最大データ数が既知ならば、メモリの使用効率は高くできる。
    • プログラミングはそのまんま。
  • 昇順配列
    • 2分探索法で検索処理O(log(N)),挿入処理O(N)
  • 配列によるヒープ
    • 検索処理O(log(N)),挿入処理(入れ替えがあるとちょっと手間)
  • 線形リスト
    • 検索処理O(N),挿入処理O(1)
    • メモリ量はデータに比例(ポインタ分のムダ)
    • スタックや待ち行列などで、最大データ数が分からない場合に便利。
  • 循環リスト
    • 待ち行列など
  • 双方向リスト
    • エディタなどの前後移動のあるデータ
  • 2分木
    • 検索処理O(log(N)),挿入処理O(1)
    • 木の左右のバランスが重要。AVL木=O(log(N)),不均衡=O(N) worst
    • 2つのポインタを持つため、メモリのムダあり。
    • 全データ対象だと再帰などでプログラミングが難しい。
  • B木
    • 検索処理O(log_d(N)),d=位数
    • データベースなどの基本技術
  • ハッシュ法
    • 検索処理:表サイズ>Nなら、O(1) , 表サイズ<Nなら、O(N)
    • 同一ハッシュ値が求まった場合=ハッシュ衝突
    • オープンアドレス法(ハッシュ値を求めなおす,イス取りゲーム?)
    • チェイン法(同一ハッシュ値をリスト構造で保存)