1. No category

情報システム基礎論２：第５回 (担当： 古賀)
SPLAY 木の計算量
2014 年 5 月 20 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
Splay 木の計算量
1
ここでは簡単のため、挿入, 削除が発生しない場合を考える。つまり、登録データは固定でそれらに対
して m 回の access が発生する場合を考える。
• n: 木のノード数
Theorem 1 m 回の access 操作を行った時の計算量は O((m + n) log n + m).
m が十分大きい時、m 回の access 操作を行った時の計算量は O(m log n) に近づく。今回の講義では Theorem
1 を「ならし計算量」という概念を導入して示す。
さらに以下の定理も成立する。
Theorem 2 m 回の access 操作を行った時の計算量は n log n + m +
Pm
j=1 log(f (j)
+ 1)。
ここで f (j) は次のように定義される。j 回目の access 操作の対象データを dj とする。dj が j 回目より前
に最後に access された時刻を i とする (i < j)。f (j) は時刻 i と時刻 j の間に access された dj 以外のデー
タ種類数。直感的には f (j) は時刻 j における dj の根からの距離。
i
j
dj 1 2 4 5 6 1 2
dj
f(j)=5
ならし計算量
2
2.1
計算量
• ti : 操作 i を実行するのにかかる実際の計算時間
• 計算量 t: m 個の操作を実行に要する総計算時間。t =
1
Pm
i=1 ti 。
2.2
ならし計算量
システム状態を数値化する関数 Φ を導入する (ポテンシャル関数と呼ばれる)。
ならし計算量 ai は、ti と操作 i による Φ の変化量との和として定義される。
ai = ti + Φ(i) − Φ(i − 1).
• Φ(i): 操作 i 実行後のポテンシャル関数の値
• Φ(i − 1): 操作 i 実行前のポテンシャル関数の値
t=
m
X
ti =
i=1
m
X
(ai + Φ(i − 1) − Φ(i)) =
i=1
m
X
ai + Φ(0) − Φ(m).
i=1
なので、Φ(0) − Φ(m) がわかれば、ならし計算量 ai の総和から t を求められる。
Theorem 1 の証明
3
3.1
ポテンシャル関数 Φ
木においてノード x を根とする部分木に含まれるノード数を s(x) とする。
Definition 3 ノード x のランク r(x) = log2 s(x)。r(x) は x が根に近いほど大きい。
以降の議論では対数の底 2 は省略して記述する。
Definition 4
Φ=
n
X
r(x).
x=1
Φ はすべてのノードのランクの合計。木がバランスしていないほど大きい。
3.2
証明の流れ:
Theorem 1 m 回の access 操作を行った時の計算量は O((m + n) log n + m).
1. 1 回の access のならし計算量は 3 log n + 1 以下。つまり、∀i, ai ≤ 3 log n + 1。
2. m 回 access を繰り返した時のならし計算量は
m
X
ai ≤
i=1
m
X
(3 log n + 1) ≤ 3m log n + m
i=1
3. ポテンシャルの変化 (Φ(0) − Φ(m)):
任意のノード x に対して 0 ≤ r(x) ≤ log n。したがって、Φ には上限値と下限値が存在し、0 ≤ Φ ≤
n log n. よって、
Φ(0) − Φ(m) ≤ n log n
2
よって、求める計算量 t ≤ (3m + n) log n + m。従って、t = O((m + n) log n + m)。
重要なのは
• 個々の ti は O(log n) より大きい可能性も小さい可能性もある。
P
• しかし、m 回の操作を実行する時間 t = m
i=1 ti は O(m log n)。すなわち、1 回の操作の平均実行
時間は O(log n)。
3.3
accesss 操作 1 回のならし計算量
データ x への access は
• 前半： x を発見するまで根からリンクを辿る作業
• 後半： move-to-root で x を根まで移動する作業
で構成されるが、前半と後半で操作の回数は同じなので後半のみを考える。ノードを 1 つ根に近付けるコ
ストを 1 とする。
Theorem 5 ノード x を move-to-root 操作で根まで移動させた時のならし計算量 ai ≤ 3 log n + 1。
move-to-root 操作は複数回の splay 操作で構成される。
• k: splay 操作の回数
• Φj : j 回目の splay 操作後の Φ の値
• cj : j 回目の splay 操作の実コスト
ai =
k
X
cj + Φk − Φ0 =
j=1
3.3.1
k
X
(cj + Φj − Φj−1 ) =
j=1
k
X
(cj + ∆Φj ).
j=1
zig splaying のならし計算量
• cj = 1。
• 関数 r() の値が変わるのはノード x と y のみ。r(x) を splay 操作実行前の、r0 (x) を splay 操作実行
後の x のランクとする。∆Φj = r0 (x) + r0 (y) − r(x) − r(y).
– r(x) < r0 (x)
– r(y) > r0 (y)
cj + ∆Φj = 1 + r0 (x) + r0 (y) − r(x) − r(y) ≤ 1 + r0 (x) − r(x) ≤ 1 + 3(r0 (x) − r(x)).
3
x
y
zig
x
y
A
B
C
C
A
B
図 1: zig splaying
3.3.2
zig-zag splaying のならし計算量
• cj = 2。
• 関数 r() の値が変わるのはノード x と y と z のみ。∆Φj = r0 (x) + r0 (y) + r0 (z) − r(x) − r(y) − r(z).
– r0 (x) = r(z)
– r(x) < r(y)
= 2 + r0 (x) + r0 (y) + r0 (z) − r(x) − r(y) − r(z)
cj + ∆Φj
≤ 2 + r0 (y) + r0 (z) − 2r(x).
z
x
D
y
zig-zag
y
Z
x
A
A
B
B
C
D
C
図 2: zig-zag splaying
ここで以下の lemma を使用する。
Lemma 6 if x1 , x2 > 0 かつ x1 + x2 ≤ 1 ならば、2 ≤ −(log x1 + log x2 )。
s0 (y)
s0 (z)
ここで、2r0 (x) − r0 (y) − r0 (z) = −(log s0 (x) + log s0 (x) ) ≥ 2。
ゆえに、cj + ∆Φj ≤ 2(r0 (x) − r(x)) ≤ 3(r0 (x) − r(x))。
3.3.3
zig-zig splaying のならし計算量
• cj = 2。
• 関数 r() の値が変わるのはノード x と y と z のみ。∆Φj = r0 (x) + r0 (y) + r0 (z) − r(x) − r(y) − r(z).
– r0 (y) < r0 (x) = r(z)
4
z
x
y
D
zig-zig
y
A
x
A
Z
B
C
C
B
D
図 3: zig-zig splaying
– r(x) < r(y)
cj + ∆Φj
= 2 + r0 (x) + r0 (y) + r0 (z) − r(x) − r(y) − r(z)
≤ 2 + r0 (x) + r0 (z) − 2r(x).
ここで、2r0 (x) − r(x) − r0 (z) = −(log
3.3.4
s(x)
s0 (x)
0
(z)
+ log ss0 (x)
) ≥ 2。ゆえに、cj + ∆Φj ≤ 3(r0 (x) − r(x)).
move-to-root 操作の均し計算量
move-to-root 操作では zig-splaying は高々1 回のみ使用される。よって、move-to-root 操作の均し計算
量 ai は、
ai =
k
X
j=1
(cj + ∆Φj ) ≤ 1 +
k
X
3(rj0 (x) − rj (x)) = 1 + 3(rk0 (x) − r1 (x)) ≤ 3 log n + 1.
j=1
• rj (x): j 回目の splay 操作実行前の x のランク
• rj0 (x): j 回目の splay 操作実行後の x のランク
5