勉強すべきもの）
- Data Structures: Linked list, BTree B+Tree
- Sort
- Search
- Graph Algorithm
- Weighted Graph Algorithm: Spanning Trees, Shortest Pathes
- Combinational Search and Heuristic Methods
- Dynamic Programming
- C++のライブラリ: STL, Boostに実装されたアルゴリズム
The Algorithm Design Manual" by Skiena
やら、webやら。
wikiなどにあるもの)
ＢTree) http://bit.ly/Tkne1I : treeをたどれば高速検索が可能。treeの深さがバランスするよう生成する、エレガントなアルゴリズムがある。このためbalanced treeと言う意味でb treeと呼ばれる。data baseなどにも使われる。オーダ m とは、枝がm/2〜m あるものを指す。nodeの追加は分かりやすいが、nodeの削除は分かりにくく。英語サイトの図 http://en.wikipedia.org/wiki/B-tree をみると分かる。
B+Tree) http://bit.ly/TkniyA これは、アクセスが集中しがちな根を見なくても、leafのアクセスだけで、検索ができるようになっているもの。つまり、Btreeのleaf以外にあるデータをleafにも重複させて持たせている。
Sort) http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/ が分かりやすい。quickソートが速いと思われているが、実は、入っているものが特定ケタの数値であれば、基数ソート(Radix sort)の法が速いこともある。複数ケタのRadix sortのやり方は大変エレガントである。また、そうでない場合でも、quick sortの軸要素(pivot)の選択が悪くtreeが非対称に分割されると、計算量が増えるので、マージソートの法が効率が良くなる。したがって、効率の悪いバブルソートは除外するとしても、様々なやり方を覚えておいたほうが良さそうである。
投稿
