Akra Bazzi Methodのススメ(QuickSortで偏った分割の時でも漸近計算量があまり落ちないことの証明もあるよ‼️)

日本のインターネッツにある情報は分割統治法の計算量の解析がマスター定理で終わっているので, 日本がIT大国になるためにも(超大袈裟)これを日本初の記事として投稿することで全人類の分割統治力をあげていくことがこの記事の目的である。証明は行いませんがReference[1][2]を参考にしてください。

TL;DR

・Akra Bazzi Methodは分割統治法アルゴリズムの計算量を求める方法で, マスター定理よりも広いクラスの分割統治法アルゴリズムの計算量を求めることができます。

本題

※この記事ではなるべく$${O}$$と$${\Theta}$$は区別します

分割統治法の計算量は再帰的に(ある人にとっては漸化式的に), 以下のように書くことができる。

$${ T(x) = g(x) + \sum_{i=1}^{k}{a_iT(b_ix+h_i(x))} \, \text{for} \, x \ge x_0}$$
$${ T(x) \in O(1) \, \text{for} \, x \lt x_0}$$

まあ多分この式を突然ポンと出されて理解できる人はいないと思います。簡単に解説すると, 問題サイズ$${x}$$の問題は, $${a_i}$$個の問題サイズ$${b_ix+h_i(x)}$$の問題に分割して再帰的に問題を解き, 再起的な計算結果をまとめる作業$${g(x)}$$分だけ計算時間がかかるという意味です。
ちょいといくつか条件があります。まず問題サイズ$${x}$$を$${b_ix+h_i(x)}$$の問題に分割するので$${0 \lt b_i \lt1, h_i(x) \in O(\dfrac{x}{\log^2{x}})}$$である必要があります。直感的には, 何回か問題を分割して行った時に必ずある$${x_0}$$があって$${x \lt x_0}$$にならないといけないという感じです。あとは$${g(x)}$$自体の計算量は$${O(x^c)}$$のように多項式で抑えられなければなりません。このあたりはwikipedia[3]にもかかれております。

計算量の見積り方

上のように分割統治法を定式化するとき, Akra Bazzi法は以下の手順で漸近的にタイトな計算量を求めることができる

1. $${ \sum_{i=1}^{k} a_ib_i^p= 1 }$$を満たす$${p}$$を見つける。

2. すると, 漸近的にタイトな計算量は$${ T(x) \in \Theta{(x^p(1+\int_{1}^{x}\dfrac{g(u)}{u^{p+1}}du))} }$$になる(簡単！)

例

常に問題サイズ$${n}$$で, 問題サイズが常に$${(1-\alpha)n, \alpha n }$$に分割され, 統合する作業が$${\Theta{(n)}}$$となるquick sortを考えます。$${\alpha}$$の値が0や1に近づくと非常に偏った分割となりますが, この時でも$${T(n) \in \Theta(n\log{n})}$$となることを示してみます。日本のQiitaでは図を用いた証明が多いかと思います。

さて, この時$${T(n) = T((1-\alpha)n)+T(\alpha n)+cn}$$ですね。($${c}$$は定数)

手順1

$${ (1-\alpha)^p + \alpha^p = 1}$$となる$${p}$$を見つけましょう。すると$${p=1}$$とわかります。

手順2

$${n^p(1+\int_{1}^{n}\dfrac{g(u)}{u^{p+1}}du)}$$を計算すると$${n+cn\log{n}}$$となります。よって, $${T(n) \in \Theta{(n+cn\log{n})}}$$となり, $${T(n) = \Theta{(n\log{n})}}$$とわかります。すごいね

まとめ

いかがでしたか?Akra Bazzi Methodを使って簡単に分割統治法の計算量を見積もることができました！皆さんも分割統治してみてくださいね

Reference

[1]Akra, Mohamad; Bazzi, Louay (May 1998). "On the solution of linear recurrence equations". Computational Optimization and Applications. 10 (2): 195–210. doi:10.1023/A:1018373005182. S2CID 7110614.
[2]Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
[3]https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method