アルゴリズムのお勉強

最近、C++でプログラムをしており、特に習ったことが無かったアルゴリズムだが、しっかり理解しておいたほうが良いと思い勉強し始めた。メモとしてまとめる。勉強が進んだら、おいおい追記していく。

勉強すべきもの）

1. Data Structures: Linked list, BTree B+Tree
2. Sort
3. Search
4. Graph Algorithm
5. Weighted Graph Algorithm: Spanning Trees, Shortest Pathes
6. Combinational Search and Heuristic Methods
7. Dynamic Programming
8. 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が非対称に分割されると、計算量が増えるので、マージソートの法が効率が良くなる。したがって、効率の悪いバブルソートは除外するとしても、様々なやり方を覚えておいたほうが良さそうである。