アルゴリズム数理論理学
mzpのまねだ。まね。
データ構造
- array
- 配列。挿入削除にO(n)かかる。ランダムアクセスはO(1)。
- list
- 挿入削除がO(1)で行える。ランダムアクセスにO(n)かかる。
- stack
- FILO(First In - Last Out)な構造。大抵listを使って実装される。
- queue
- FIFO(First In - First Out)な構造。双方向キューは頭からも挿入削除できる。
- hash
- 挿入削除アクセスがO(1)だが、効率がデータ総量やhash関数の質に左右される。
- tree
- 枝分かれしたlistのようなもの。n分木。挿入削除アクセスがO(log n)
- heap
- 親が子よりも順序が小さい[大きい]n分木。最小値[最大値]をO(1)で参照可能。挿入削除はO(log n)、普通の探索はO(n)。優先順位付キュー。
- red-black-tree(赤黒木・2色木)
- 平衡木の一種で、挿入削除アクセスがO(n)の2-3-4木を改良して、最悪でO(log n)でできるようにしたもの。赤黒木の黒点が2-3-4木でのノードにあたる。これを念頭に置かないと赤黒木は理解できないと思われる。
探索アルゴリズム
- 2分探索
- 2分木使ってうぼぁー。O(log n)
- k番目の要素
- なんか良くわからんが中央値で分割してもぐっていくっぽい。O(n)
