教科書を借りたので、主にそれに沿って。（講義？知らんがな）
データ構造
列
配列
- アクセス $O(1)$ アドレスが計算可能
- 挿入、削除 $O(n)$ 当該データ以降をずらす
リスト
- アクセス $O(n)$ めぐるめぐるよ
- 挿入、削除 $O(1)$ つなぎ替えるだけ
スタック
アクセス可能な位置を限定したので$O(1)$。
LIFO。
待ち行列
$O(1)$。
FIFO。
木
ノードと葉からなる。
子供の数が任意である場合、子供の持ち方（順序が大事なら列、そうでなければ集合の持ち方の中から）考えなければならない。
集合
優先度付き待ち行列
取り出しを最小値に限定。ヒープを使う。
- アクセス $O(1)$
- 挿入 $O(\log n)$
2分探索木
- 深さ 平均$O(\log n)$ 最悪$n$
- アクセス $O(深さ)$
- 挿入、削除 $O(深さ)$
2-3木
ノードは実際のデータを持たない。
- 深さ $O(\log n)$
AVL木
- 深さ $O(\log n)$
ハッシュ
- $N$: もってるデータの数
- $B$: ハッシュテーブルの大きさ
- $\alpha$: $\frac N B$
- ハッシュ関数: データのキーを引数に、$0 \le i \lt n$なる$i$を理想的には同様に確からしく返す関数。
チェイン
$N < 2B$が崩れたら、そろそろハッシュテーブルを大きくしてもいいかなーって。
- アクセス、追加、削除 $\alpha + 1$
オープンアドレス
こっちは$N < 0.9B$が崩れたら、そろそろ危ないかな。
- 追加 $\frac 1 {1 - \alpha}$
- 存在が保証されているデータの参照、削除 $\frac 1 \alpha \log_e \frac 1 {1 - \alpha}$
集合群
-
merge, findが可能
-
ポインタに依る実装: merge: $O(1)$, find: $O(n)$ (findは、経路圧縮とかするとずっとはやくなる)
-
IDによる実装: merge: $O(n)$, find: $O(1)$
アルゴリズム
ソート
バブルソート
- $O(n^2)$
クイックソート
教科書では、pivotとして最初の2要素の大きい方とし、それ未満を左側においている。
- 平均$O(n \log n)$、最悪$O(n^2)$
マージソート
- $O(n \log n)$
ヒープソート
単純にヒープに入れて出すのでも良いが、教科書ではヒープづくりを$O(n)$にがんばっている。
- $O(n \log n)$
バケットソート
データの変域が有限で決まっているときに、そのサイズの配列を作れば線形時間にできる。
- $O(n)$
基数ソート
バケットソートを応用して、これを繰り返しすればそこまでメモリを食わずにだいたい線形時間。
- 近似して$O(n)$
グラフ
最短路
ダイクストラ（単一始点）
負のコストがあるとつらい。
単純なダイクストラ
- $O(v^2)$
優先度付待ち行列のダイクストラ
- $O((e+v)\log v)$
単純なダイクストラより良いとは限らない。単純グラフにしたとして、$e = O(v^2)$。
フロイド (全始点）
- $O(v^3)$
一列化
帰りがけでやるだけ。
強連結成分分解
帰りがけでやって、辺をえいってやって、やるだけ。
最小木
プリム
任意の点からダイクストラ的な。$O(v^2)$
クラスカル
コストの小さい方から辺でループを回して、つなげても極大木になるかなって。$O(e \log e)$
関節点
- O(v+e)
$ord$を行き掛けに、$low = \min ( ord[自分], ord[後退辺の先], low[子] )$を帰りがけに求めて、
根でない$v$が関節点 $\Leftrightarrow \exists w \in \{vの子ノード\}, ord[v] \le low[w]$
根は、２つ子をもってたら関節点。
文字列
力まかせ
- O(mn)
KMP
検索文字列の文字それぞれに対してskip数を定める。
そこでマッチしなくなったらskipだけとばす。
- 文書中のポインタは逆戻りしないので、$O(n)$
BM
文書中のポインタは前から後ろにすすめるが、そのなかで検索文字列と一致するか調べるときは後ろから比較していく。
不一致のとき、文書側の文字がなにであるかと、検索文字列側のどこで不一致になったかでスキップできる量を測り、大きい方だけスキップする。
- うまくいくと$O(n/m)$
appendix
今回のテスト以降、見ることはないんじゃなかろうか。
オープンアドレス法における挿入回数の見積もり
ある位置に要素が入っている確率は同様に確からしく、$\alpha = \frac B N$。
よって、挿入時、再ハッシュが起きる回数つまり衝突する回数がちょうど$i$である確率は、
ちょうど$\alpha ^ i - \alpha ^ {i+1}$くらい。($i$回は衝突したが、$i+1$回目は衝突しなかった。)
ちょうど$i$回衝突したなら計算量は$i+1$らしいので、期待値は、
$\sum_{i=0}^{\infty} {(i+1)(\alpha^i - \alpha^{i+1})} = \sum_{i=0}^{\infty} { (i\alpha^i - (i+1)\alpha^{i+1})} + \sum_{i=0}^{\infty} {\alpha^i} = 0 - 0 + \frac 1 {1-\alpha} = \frac 1 {1-\alpha}$