『簡潔データ構造』
2章
RAM と word-RAM の違い
RAM は一つのメモリセルには任意の桁の数が格納できるが、word-RAM には一つのメモリセルには1ビットしか格納できない
note.icon RAM 使い物にならない気がする
word-RAM は、U ビット並んでいて、各ビットへはそのビットのインデックスでアクセスすることができて、lg U ビットを1ステップで取得・格納・演算することができるようなモデル
節点数 n の2分木は Θ(n lg n)
各節点に番号をつけると、その接点を指すポインタのサイズは lg n ビットになる
語長ではないので注意
各節点には、ルートを除いて別の節点からのポインタがついているので、木全体では n - 1 個のポインタがある
なので $ (n - 1) lg \ n になる
Θの定義から、$ \Theta((n - 1) \ lg \ n) = \Theta(n \ lg \ n)
大きい n を取るので、 $ n \ lg \ nに比べて $ lg \ n は無視できる
計算量の記号 (このページよりも本の定義を見たほうがわかりやすいと思う)
注: c は正の実数
O(g(n)): g(n) と同じかより小さい f(n) の集合
Ω(g(n)): g(n) と同じかより大きい f(n) の集合
Θ(g(n)): g(n) と (定数倍を無視して) 同じ f(n) の集合
o(g(n)): g(n) よりも小さい f(n) の集合
この集合の要素は、n が大きくなったとき、g(n) に対して無視できるようになるというのが重要
あと $ s = n + o(f(n)) の = は notation (型あってないので)
対数多項式関数
$ lg^c x は $ (lg \ x)^c のこと
3章
インデックスは1から
rank_0(B, i): B[1..i] 中の0の数 (rank_1 なら1の数)
B=010101 なら、rank_0(B, 3) = 2
select_0(B, j): 先頭から j 番目の0の位置 (select_1 なら 1 の位置)
B=010101 なら、 select_0(B, 3) = 5
rank の計算
大ブロック: l = lg^2 n
本の例は lg^2 n になっていない気がする…？ lg^2 n なら大きすぎない？
select の計算
n=16, 1111111111111111 を考える (密になる)
...
完全n分木の内部ノードの数
深さ d の内部ノードの数を$ I_dとすると、
$ I_d = I_{d-1} + (n - 1) I_{d-1} + 1 ($ I_0 = 0)
$ \sqrt{lg \ n} 分木で、d は葉の数が $ 2 lg^3 nなので 6,7あたりとすると内部ノードの数は $ lg^3 n くらいになる？
ビットベクトル全体での内部ノードの数は O(n/s)
question.icon なぜなのかわからん…
各大ブロックに対し、対応するデータ構造へのポインタを格納する。これは $ O(lg \ n * (n / l))
question.icon 意味不明
誤植かと思ったところ
p.9 $ \frac{1}{2}lg \frac{u}{n(u-n)}の最大値と最小値 ($ 0 < n < u)
最大値はn=1,u=2のときで $ \frac{1}{2}、最小値はu=2nのときで $ \frac{1}{2}lg \frac{2}{n}な気がする
示したいことは成り立つのでOKではある