データ構造をマージする一般的なテク

マージテクと略されます

本家の
“データ構造をマージする一般的なテク” とは?
をまとめます

2つのデータ構造から,新しいデータ構造が算出できるという状況を考えます

これをマージといいます

マージするとデータ構造のサイズがもとのサイズの合計になることが前提です

データ構造を今後グループと単に呼んだりします

合計サイズを O(N)O(N) としておきましょう

マージ時の計算量が

  • どちらか好きな方のサイズに依存するか
  • 大きい方のサイズに依存するか

によって主に2種類あります

いずれにせよ依存するサイズを nn とすると nf(n)nf(n) の時間がかかるとしましょう

f(n)f(n)は大抵 11logn\log n になります

どちらか好きな方のサイズに依存する

この場合,適切にswapなどをして小さい方のサイズに依存するようにします(この時,依存される方を「なめられる」とよくいわれます,使います)

このとき,全体では O(NlogNf(N))O(N \log N \cdot f(N)) となります

証明

グループにサイズと同じ量の要素があると考え,
各要素について見ていきます

ある要素がなめられるとき,その要素が属するグループは必ず2倍以上の大きさになります

よって,全体で O(logN)O(\log N) 回しかなめられません(O(logN)O(\log N)回のマージでサイズがNNになるため)

なので合計で O(NlogN)O(N\log N) 回しかなめられません

f(n)f(n)については,f(n)=1f(n) = 1なら上記の議論でいいのですが,
そうでないときはちょっとよくわからなかったので帰納法で示します

(追記: 証明を置き換え法によるちゃんとしたものに変えておきました)

最悪実行時間をT(N)T(N)として,T(N)=O(Nlog2Nf(N))T(N) = O(N \log_2 N \cdot f(N)) を証明します

T(N)=cNlog2Nf(N)T(N) = c \cdot N \log_2 N \cdot f(N)を小さいNNに対して仮定し,T(N)cNlog2Nf(N)T(N) \leq c \cdot N \log_2 N \cdot f(N) が示せればよいです.ccは適切な定数とします.cdc \geq dであるとよいことを先に書いておきます.ddも定数で,O(n1f(n1))=dn1f(n1)O(n_1f(n_1)) = d \cdot n_1 f(n_1) としておきます

ところで,NNの区間をn1+n2=Nn_1 + n_2 = Nと分割できるとして,n1n2n_1 \leq n_2として一般性を失いません

T(N)=dn1f(n1)+T(n1)+T(n2) \begin{aligned} T(N) = d \cdot n_1 f(n_1) + T(n_1) + T(n_2) \end{aligned}

となります

右辺を上から押さえます

n1f(n1)+T(n1)+T(n2)=dn1f(n1)+cn1log2n1f(n1)+cn2log2n2f(n2)dn1f(n1)+cn1log2N2f(n1)+cn2log2n2f(n2)=dn1f(n1)+cn1(log2N1)f(n1)+cn2log2n2f(n2)cn1log2Nf(n1)+cn2log2n2f(n2)cn1log2Nf(N)+cn2log2Nf(N)=c(n1+n2)log2Nf(N)=cNlog2Nf(N) \begin{aligned} &n_1 f(n_1) + T(n_1) + T(n_2) \\ &=d \cdot n_1f(n_1) + c\cdot n_1 \log_2 n_1 \cdot f(n_1)+ c\cdot n_2 \log_2 n_2 \cdot f(n_2) \\ &\leq d \cdot n_1f(n_1) + c\cdot n_1 \log_2 \frac{N}{2} \cdot f(n_1)+ c\cdot n_2 \log_2 n_2 \cdot f(n_2)\\ &= d \cdot n_1f(n_1) + c\cdot n_1 (\log_2 N - 1) \cdot f(n_1)+ c\cdot n_2 \log_2 n_2 \cdot f(n_2)\\ &\leq c\cdot n_1 \log_2 N\cdot f(n_1)+ c\cdot n_2 \log_2 n_2 \cdot f(n_2)\\ &\leq c\cdot n_1 \log_2 N\cdot f(N)+ c\cdot n_2 \log_2 N \cdot f(N)\\ &= c\cdot (n_1 + n_2) \log_2 N\cdot f(N)\\ &= c\cdot N \log_2 N \cdot f(N) \end{aligned}

ただし,境界条件は省略する

途中,n1N2n_1 \leq \frac{N}{2} を使いました

どのように分割されていっても大丈夫ということがわかりました

O(NlogNf(N))O(N\log N \cdot f(N)) を達成できます


たとえば f(n)=O(logN)f(n) = O(\log N) (これは大抵大きい方のサイズに依存するため logN\log N でうえから抑える) ならO(Nlog2N)O(N \log^2 N) になります

大きい方のサイズに依存する

この時,マージする順番を決められる場合は,

小さい方から2つずつをマージする

とすることで,O(NlogNf(N))O(N \log N \cdot f(N))を達成できます

順番変えられないなら無理です

このパターンのマージは,両グループの要素すべてをなめると考えると証明しやすいです

こちらのパターンは両方のグループが「なめられる」と考えるとうまくいきやすいと思います

証明(f(n)=1のときだけ)

ある大きさnnのグループは2回マージすると二倍の大きさになります

ならないと仮定すると,2回マージしたグループのサイズをn1,n2n_1,n_2とおくと,
n1+n2<nn_1 + n_2 \lt nとなりますが,

n1,n2<nn_1,n_2 \lt n なため,マージする順序の決め方より,この2つは先にマージされているはずです

以上,背理法より,2回マージすると二倍の大きさになることがわかります

よって,初期状態での,あるグループがマージされる回数は O(logN)O(\log N)程度です
このグループの要素nn個のなめられる回数の合計はO(nlogN)O(n \log N)です

すべてのグループについてそれが言えて,マージ毎に各要素がなめられるので,O(NlogN)O(N \log N)がいえます

f(n)=O(1)f(n)=O(1)については以上でよくて,そうでない場合ですが,よくわかりません

f(n)=O(logn)f(n) = O(\log n) のとき O(Nlog2N)O(N \log^2 N) と聞きますし,実際速いんですが,計算量がどうなるかわかりません

えーなんか

もともとるまライブラリに加える予定だったんですが,ちょっと雑というか,f(n)f(n)の要件もよくわからないですし,計算量の正確な値もよくわかりませんでした

まあ多分,f(n)f(n)は広義単調増加,というのはいいと思います (もしくは計算量がO(f(n))O(f(n))であるとすると仮定する)

趣旨としては,マージテクをまとめて,そして,証明を書きたい,というものでした

もうちょっとまとまったら,るまライブラリに昇格しょうと思います

このブログの人気の投稿

Veturのエラー解決

分割統治とマスター定理の紹介