分割統治法の計算量

分割統治法とは

与えられた問題Pがあったとき、これを小さな問題に分割して処理をしようという発想。

データベースのインデックスなどに用いられる二分探索なども分割統治法の考え方に基づいている。

実際の計算量を式で表し、アルゴリズムの有効性を検証してみる。

分割統治法の計算量算出

ここで、与えられた問題Pのサイズを$n = 2^m$とする。

これは言い換えると以下のように表せる。

$$\log_2 n = m ・・・①$$

いま、サイズnの問題Pを$α(n)$時間で解くアルゴリズムがあるとする。

また、サイズnの問題を$\frac{n}{2}$の部分問題P1,P2に分割するのにかかる時間をたかだかn時間。
P1,P2の解からPの解を構成するのにたかだかn時間と仮定する。

このとき、問題PをP1,P2に分割して問題を解く実行時間は以下になる。

$$n + 2α ( \frac{n}{2} ) + n$$

さらにこれを$\frac{n}{4}$に分解して解く実行時間は以下。

$$n + 2( \frac{n}{2} + 2α(\frac{n}{4}) + \frac{n}{2}) + n = 2n + 4α(\frac{n}{4}) + 2n$$

さらにこれをm回分割するとして一般化すると以下のような式になる。

$$mn + 2^mα(\frac{n}{2^m}) + mn$$

これに①を代入すると

$$n\log_2 n + 2^{\log_2 n}α(\frac{n}{2^{\log_2 n}}) + n\log_2 n$$

式をまとめると、

$$2n\log_2 n + nα(1)$$

よって分割統治法のオーダーは

$$O(n\log_2 n)$$

オーダーからみた有効性

計算量が$2n\log_2 n + nα(1)$なことから分かるが、アルゴリズムαのオーダーが仮に$n^2$や$n^3$だった場合は分割統治法は非常に有効に作用することがわかる。

しかし、αのオーダーが$n$等の場合は、逆にパフォーマンスが悪化させてしまう可能性があるので、杓子定規に何でもかんでも分割統治法を適用すればパフォーマンスが上がるわけではないので注意が必要。