てけノート

on the foot of giants

【読書メモ】アルゴリズムとデータ構造

      2015/10/17


まとめとかないと忘れそうなので、メモ。
プログラミングやるなら知っておくべき最低限。
超良書。

Amazonへ

第一章 ソート

・バブルソート:左右比較、while { for { if左>右⇒ひっくり返す
・クイックソート:基準決めて左右に振り分け。for { if(基準値>それ それ⇒基準値の左、else それ⇒基準値の右   2つに分割し以下再帰。速度不安定 qsort
・マージソート;再帰でブロックごとに分割し、隣接ブロックごとにソートして結合を繰り返す。速度安定 stable_sort
・コームソート;交換する距離(gap)を固定してバブルソート。だんだんgapを小さくする。速度不安定
・挿入ソート:ソート済み配列に新しく配列を足すとき、挿入箇所を探して挿入を繰り返す。

第二章 サーチ

・リニアサーチ:一つずつ if(ほしい=それ or NOT を繰り返す
・バイナリサーチ:ソート済配列に対し、if(ほしい>配列の真ん中 or NOT を繰り返し、次の配列範囲で再帰

第三章 リスト

配列と比較したPros:挿入と削除 Cons:検索とか
typedef struct tlNode{
struct tlNode *prev;
struct tlNode *next;
int data;
}ListNode

第四章 スタック&キュー

スタック:後ろからとる、後ろに追加。かっこの対応の検索、かっこ付きの計算をとく
キュー:頭からとる、後ろに追加。プリンタのジョブなど。環状のリングバッファにより配列長はムシできる。

第五章 再帰呼び出し

a,b,c,dの最大公約数gcd(a,gcd(b,gcd(c,d))))など。

第六章 ツリー構造

複数ポインタをもつリスト。二分木の場合:
typedef struct ttNode{
int value;
struct ttNode *left;
struct ttNode *right;
}tree_node;
left < 自分 < rightが常に成り立つ。 Pros:追加、サーチ、削除。 map:keyとvalueをセットにするとサーチ楽。ttNodeにstring keyを追加。 平衡木:木の長さがバランスよくなるように回転できるもの。AVL木とB木、B+木が素晴らしい

第七章 ハッシュマップ

Pros:追加、サーチ、削除。高速なデータ構造
key, value, etc…
ハッシュ値 = keyから生成した値 % ハッシュ表長
ハッシュ表長は素数がよい。
衝突時には二分木などで対策。

第八章 浮動小数点と数値計算

でかいのと小さいの一緒に計算しない
数値計算では:バイナリサーチorニュートン法
バイナリサーチ:
mid = left + right / 2
if(mid > 0) right = mid, else left = mid
while err > tolerance
ニュートン法:微分繰り返す、局所解にトラップされるリスク

第九章 文字列検索

KMP法:一致しないことを知ってる部分と一致することを知ってる部分をスキップ
BM法:キーの終わりから比較し、末尾が一致するとこまでスキップ。ただしif(back) 一文字進むなどスキップしすぎ注意

第十章 バックトラック法と幅優先探索

バックトラック法:再帰使って試行錯誤。depth優先。エイトクイーン問題など
幅優先探索法:ターン制で再帰。7パズル、将棋の手とか。盤面を記録してDB追加

第十一章 動的計画法

一番少ないおつり問題、ナップザック問題、最短経路問題など
for i{ for j=size[i]{ new = current[j – size[i]] + value[i] } if(new > current { current[j] = new

第十二章 アルゴリズムで遊ぶ

逆ポーランド記法

第十三章 グラフ構造

有向グラフと無向グラフ
隣接リスト:個別に隣接しているやつを検索しやすい
隣接行列:全体でどことどこが隣接しているかみやすい
ダイクストラ:最短経路問題。動的計画

 

 - プログラミング, 読書