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

線形探索法と2分探索法とハッシュ法の短所を比較

短所

• 線形探索法はデータを登録順に保存しているが、探索が遅い
• 2分探索法は探索が線形探索より早いが、あらかじめソートが必要だし、データの登録順を保存できない
• ハッシュ法はハッシュ関数が便利だが、データを格納する配列が肥大化したり、データの衝突を検出、考慮したりする必要がある。また、データの登録順は保存できない。

アルゴリズムの選択は問題次第である、ということ

• Oの小さいアルゴリズムは凝ったものが多い
• Oが極めて小さい場合には、凝ったアルゴリズムより、素朴なアルゴリズムの方が早い
• プログラミングの手間も考えよう
• めったに使わない部分は素朴なアルゴリズムでよい
• 実行時間とデータ領域のトレードオフも考えよう

定数係数

アルゴリズムの勉強時に定数係数と出てきたら、計算機の速度や、実装言語の選択や、高速なコンパイラなど、アルゴリズム自体ではなくアルゴリズムを運用・実装する環境の早さのことをさしている。

計算量の話は不可避

アルゴリズムの勉強をするときには計算量を常に考えよう。
一般に、プログラムの速さをあげる方法として定数係数を下げるような方法が選ばれることが多い。

• 早いマシンに乗り換え
• cやアセンブラで記述
• コンパイラを早いものに

でも、このアプローチでは実際には計算量のオーダーは改善されない。
オーダーのことも考えようね。