]> アルゴリズムイントロダクション第 9 章中央値と順序統計量 (補足)

中央値と順序統計量 (補足)

nanto_vi (TOYAMA Nao)

4 つずつのグループに分割した場合

[4 つずつのグループに分割した場合の x より小さい要素、大きい要素の個数を表した図]

x より大きい要素、小さい要素はそれぞれ少なくとも $3 (⌈\frac{1}{2} ⌈\frac{n}{4}⌉⌉ - 2) \geq \frac{3 n}{8} - 6$ , $2 (⌈\frac{1}{2} ⌈\frac{n}{4}⌉⌉ - 1) \geq \frac{n}{4} - 2$ 個存在するから、 $A_{smaller}$ , $A_{larger}$ の要素数はそれぞれ高々 $\frac{5 n}{8} + 6$ , $\frac{3 n}{4} + 2$ 個。よって、 $\begin{array}{l} T (n) \leq T (⌈\frac{n}{4}⌉) + T (\max (\frac{5 n}{8} + 6, \frac{3 n}{4} + 2)) + O (n) \\ = T (⌈\frac{n}{4}⌉) + T (\frac{3 n}{4} + 2) + O (n) \end{array}$

$O (n)$ はある定数 a を用いて $a n$ で抑えられる。ここで、ある定数 c に対して $T (n) \leq c n$ と仮定すると、 $\begin{array}{l} T (n) \leq c ⌈\frac{n}{4}⌉ + c (\frac{3 n}{4} + 2) + a n \\ \leq c (\frac{n}{4} + 1) + c (\frac{3 n}{4} + 2) + a n \\ = c n + 3 c + a n \\ > c n \end{array}$

よって、 $T (n)$ を $c n$ で抑えきれない。

6 つずつのグループに分割した場合

x より大きい要素、小さい要素はそれぞれ少なくとも $4 (⌈\frac{1}{2} ⌈\frac{n}{6}⌉⌉ - 2) \geq \frac{n}{3} - 8$ , $3 (⌈\frac{1}{2} ⌈\frac{n}{6}⌉⌉ - 1) \geq \frac{n}{4} - 3$ 個存在するから、 $A_{smaller}$ , $A_{larger}$ の要素数はそれぞれ高々 $\frac{2 n}{3} + 8$ , $\frac{3 n}{4} + 3$ 個。よって、 $\begin{array}{l} T (n) \leq T (⌈\frac{n}{6}⌉) + T (\max (\frac{2 n}{3} + 8, \frac{3 n}{4} + 3)) + O (n) \\ = T (⌈\frac{n}{6}⌉) + T (\frac{3 n}{4} + 3) + O (n) \end{array}$

$O (n)$ はある定数 a を用いて $a n$ で抑えられる。ここで、ある定数 c に対して $T (n) \leq c n$ と仮定すると、 $\begin{array}{l} T (n) \leq c ⌈\frac{n}{6}⌉ + c (\frac{3 n}{4} + 3) + a n \\ \leq c (\frac{n}{6} + 1) + c (\frac{3 n}{4} + 3) + a n \\ = \frac{11 c n}{12} + 4 c + a n \\ = c n - (\frac{c n}{12} - 4 c - a n) \\ = c n - (\frac{c - 12 a}{12} n - 4 c) \end{array}$

ここで、 $c > 12 a$ とすると、 $n \geq \frac{12}{c - 12 a} 4 c = 48 + \frac{576 a}{c - 12 a}$ で $T (n) \leq c n$ だから、 $T (n) = O (n)$

Lazy-Select

Select は $O (n)$ に隠された定数が大きいため、一般には Randomized-Select または Lazy-Select が用いられることが多いらしい。

$\begin{aligned} Lazy-Select (A, i) \\ 1 & n \leftarrow A の要素数 \\ 2 & if n < d (d はある定数) \\ 3 & then A を任意の方法でソート \\ 4 & return A [i] \\ 5 & B \leftarrow A からランダムに選んだ n^{\frac{3}{4}} 個の要素 \\ 6 & j \leftarrow i \frac{n^{\frac{3}{4}}}{n} = i n^{- \frac{1}{4}} \\ 7 & l \leftarrow Lazy-Select (B, \max (⌊j - \sqrt{n}⌋, 1)) \\ 8 & h \leftarrow Lazy-Select (B, \min (⌈j + \sqrt{n}⌉, n^{\frac{3}{4}})) \\ 9 & A_{1} \leftarrow h より小さい A の要素 \\ 10 & A_{2} \leftarrow h より大きい A の要素 \\ 11 & t \leftarrow A_{1} の要素数 + 1 \\ 12 & if i = t \\ 13 & then return h \\ 14 & if i > t \\ 15 & then return Lazy-Select (A_{2}, i - t) \\ 16 & A_{1, 1} \leftarrow l より小さい A_{1} の要素 \\ 17 & A_{1, 2} \leftarrow l より大きい A_{1} の要素 \\ 18 & s \leftarrow A_{1, 1} の要素数 + 1 \\ 19 & if i = s \\ 20 & then return l \\ 21 & if i < s \\ 22 & then return Lazy-Select (A_{1, 1}, i) \\ 23 & return Lazy-Select (A_{1, 2}, i - s) \end{aligned}$

Randomized-Partition

$\begin{aligned} Randomized-Partition (A, p, r) \\ 1 & i \leftarrow Random (p, r) \\ 2 & 値の交換 A [r] \leftrightarrow A [i] \\ 3 & return Partition (A, p, r) \end{aligned}$

$\begin{aligned} Partition (A, p, r) \\ 1 & x \leftarrow A [r] \\ 2 & i \leftarrow p - 1 \\ 3 & for j \leftarrow p to r - 1 \\ 4 & do if A [j] \leq x \\ 5 & then i \leftarrow i + 1 \\ 6 & 値の交換 A [i] \leftrightarrow A [j] \\ 7 & 値の交換 A [i + 1] \leftrightarrow A [r] \\ 8 & return i + 1 \end{aligned}$

スタッフロール

Slide Composer: nanto_vi
Master of Ceremony: motemen
Venue Provider: Hatena Inc.
Rehearsal Collaborator: NISHIDA Atsushi
Exploded: hakobe932; ninjinkun; ujihisa; And You