定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-3

文献購読

2-2-3はデータ挿入のコストの話。
そうか、検索だけじゃなくて挿入のコストを考えなきゃいけないときも多いよな。

リニアとバイナリのデータ挿入における違い。

リニアはソート不要なので、リストの最後にデータをくっつけるだけ。
一方、バイナリは常にリストがソートされてなきゃ駄目なので、
素朴なアプローチとしては、新しいデータの挿入位置を決めて
挿入位置より後ろのデータを後ろにずらす。
そして、開いた場所に新しいデータを入れることになる。

実装

add_linear(int key, int data){
  /*nはデータ個数（データの挿入位置をあらわす配列番号*/
  if(n >= TABLE_SIZE){ error("too much data.");}
  table[n].key = key;
  table[n].data = data;
}

add_binary(int key, int data){
  int pos;
  pos = 2分探索で挿入位置決定

  配列のpos以降を1つづつずらす

  table[pos].key = key;
  table[pos].data = data;  
}

n個のデータを追加するための計算量

  • バイナリはn回末尾に挿入するだけなのでO(n)
  • リニアは、1回の計算に必要な計算量を考えると、挿入位置探索にO(log n)、データずらしは線形時間なのでO(n/2) = O(n)となり、O(max(log n, n, 1))でO(n)も必要になる。さらにこれをn回繰り返すので、合計計算量はO(n^2)となる。

実運用時のことを考える

2分探索法は挿入と検索を同時に行う必要がある場合には向かないことが分かる。
だが、2分探索法は挿入時のコストを軽減することができれば、問題が減りそうだ。

どんなときにコストを減らせる?

最初にすべてのデータをソート可能で、メインでは検索のみの場合

どうやるの？
  • 最初はデータをソートせずに配列に挿入する。
  • ソートには計算量がO(n log n)のアルゴリズムがあるので、それを使ってソートする
結果は？

結果として挿入にかかるコストがO(n^2)からO(n log n)に激減した。