2021年8月25日水曜日

Treapのunionの計算量に関するメモ

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf にm,n (m≤n)m, n \ (m \le n)要素のTreapのunionで期待計算量がO(mlog⁡(n/m)){O}(m \log (n/m))であるものが紹介されている。これを使うと次のことができる:

1要素のTreapがNN個与えられたとし、これらのTreapに任意の順番でN−1N-1回unionを適用してNN要素のTreapを作るとする。この時、全体の期待計算量はO(Nlog⁡N){O}(N \log N)である。

これはマージテクと同じように理解できる:

まず、定数BBが存在してm,n (m≤n)m, n\ (m \le n)要素のTreapのunionの期待計算量はBmlog⁡(n/m)B m \log (n/m)以下である。

求める計算量をT(N)T(N)とする。C>0C>0が存在してNN未満の整数xxについてはT(x)≤Cxlog⁡xT(x) \le C x \log xが成り立っていると仮定する。このとき、T(N)≤CNlog⁡NT(N) \le C N\log Nであることを示せばよい。この際、C≥BC \ge Bとしてよい。

T(N)≤max⁡m+n=N(Bmlog⁡nm+T(m)+T(n)) T(N) \le \max_{m+n = N} \bigl (Bm \log \frac{n}{m}+ T(m) + T(n) \bigr)

であるから、任意の分割N=m+n (0<m≤n)N = m+n \ (0 < m \le n)についてBmlog⁡(n/m)+T(m)+T(n)≤CNlog⁡NBm \log (n/m) + T(m) + T(n) \le C N \log Nが成り立つことを示せばよい。実際、次のように示せる:

Bmlog⁡nm+T(m)+T(n)≤ Bmlog⁡nm+Cmlog⁡m+Cnlog⁡n≤ C(mlog⁡nm+mlog⁡m+nlog⁡n)= C(mlog⁡nm+mlog⁡m+nlog⁡nmm)= C(mlog⁡nm+mlog⁡m+nlog⁡nm+nlog⁡m)= C((m+n)log⁡nm+(m+n)log⁡m)= C(Nlog⁡nm+Nlog⁡m)= C(Nlog⁡n−Nlog⁡m+Nlog⁡m)= CNlog⁡n≤ CNlog⁡N \begin{aligned}& Bm \log \frac{n}{m}+ T(m) + T(n) \\ \le \ & B m \log \frac{n}{m} + Cm\log m + C n \log n \\ \le \ & C \bigl (m\log\frac{n}{m} + m\log m + n \log n \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n \log \frac{n}{m}m \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n\log \frac{n}{m} + n \log m \bigr ) \\ = \ & C \bigl ((m+n) \log \frac{n}{m} + (m+n)\log m \bigr ) \\ = \ & C \bigl (N\log \frac{n}{m} + N \log m \bigr) \\ = \ & C(N\log n - N\log m+ N \log m) \\ = \ & CN\log n \\ \le \ & CN\log N \\ \end{aligned}

（log⁡1=0\log 1 = 0 問題があるのであまり正確でない。）

投稿者