投稿日時：2020/03/10 13:51

最終更新日時：2020/03/10 13:51

分割統治法の計算量

はじめに

　分割統治法などを用いることで最悪計算量 $T(n)$ のアルゴリズムが

\begin{dcases}T(1)=O(1) & (n=1) \\T(n)=2T\left(\frac{n}{2}\right)+O(n) & (other)\end{dcases}

のようになる場合がある。この漸化式を解くことにより $T(n)=O(n\log{n})$ が得られ、例えば、クイックソートやFFTなどがこのようになる。
　今回はその計算量について述べる。

　全然興味がないから知らないけど、競技プログラミングにおける最重要項目の1つではないだろうか。むしろ基礎知識だからこの記事を読む必要すらないともとれる。

　今回の記事は以下の図書を参考に書いているので気になる人は読んでみるといいだろう。ただし、日本語訳が怪しい部分もあるため考えどころである。私には買うお金がないので図書館で読んだ。

漸近記法

　よく知っている人は飛ばすべきである。
　まずは計算量を記述するための漸近記法について定義を与える。

定義

　 $f(n)\in O(g(n))$ となるとは

\exist n_{0}>0,\exist c>0\ s.t.\ \forall n>n_{0},0\leq f(n)\leq cg(n)

を満たすことである。このとき、 $g(n)$ は $f(n)$ の漸近的上界(asymptotic upper bounds)であるという。

　これはランダウのO-記法としても知られている。次に、下界についての定義を示す。

定義

　 $f(n)\in\Omega(g(n))$ となるとは

\exist n_{0}>0,\exist c>0\ s.t.\ \forall n>n_{0},0\leq cg(n)\leq f(n)

を満たすことである。このとき、 $g(n)$ は $f(n)$ の漸近的下界(asymptotic lower bounds)であるという。

　また、下界かつ上界について以下の定義が与えられる。

定義

　 $f(n)\in\Theta(g(n))$ となるとは

\Theta(g(n))=O(g(n))\cap\Omega(g(n))

を満たすことである。このとき、 $g(n)$ は $f(n)$ の下界かつ上界であるもしくは漸近的にタイトな限界(asymptotically tight bounds)という。

　これらの定義の相違についてを記す。まずは $f(n)\in\Theta(g(n))$ であるとき、十分に大きな全ての $n$ で正の $c_{1}>0,c_{2}>0$ が存在して

c_{1}g(n)\leq f(n)\leq c_{2}g(n)

を満たすため、

\lim_{n\to\infty}\frac{f(n)}{g(n)}=c_{3}

を満たす有限の極限値 $c_{3}(c_{3}\neq 0)$ をもつ。これは $\Theta(g(n))$ の定義と同値な表現である。特に、 $c_{3}=1$ であるとき $f(n)$ と $g(n)$ は漸近的に等しいという。次に、 $f(n)\in O(g(n))\setminus\Theta(g(n))$ であるときを考えれば、十分に大きな全ての $n$ で

f(n)\leq c_{2}g(n)

を満たす $c_{2}>0$ のうち

c_{1}g(n)\leq f(n)\leq c_{2}g(n)

を満たす $c_{1}>0$ が存在しないものとなる。すなわち、十分に大きな $n$ では任意の $c$ で

0\leq f(n)< c_{2}g(n)

であるということである。つまり、

\lim_{n\to\infty}\frac{f(n)}{g(n)}=0

を満たす。同様にして、 $f(n)\in\Omega(g(n))\setminus\Theta(g(n))$ を考えれば

\lim_{n\to\infty}\frac{g(n)}{f(n)}=0

である。これより、以下の定義が与えられる。

定義

　 $f(n)\in o(g(n))$ となるとは

o(g(n))=O(g(n))\setminus\Theta(g(n))

を満たすことである。また、これは

\exist n_{0}(n_{0}>0),\forall c(c>0)\ s.t.\ \forall n(n>n_{0}),0\leq f(n)< cg(n)

および

\lim_{n\to\infty}\frac{f(n)}{g(n)}=0

を満たすことと同値である。

定義

　 $f(n)\in\omega(g(n))$ となるとは

\omega(g(n))=\Omega(g(n))\setminus\Theta(g(n))

を満たすことである。また、これは

\exist n_{0}(n_{0}>0),\forall c(c>0)\ s.t.\ \forall n(n>n_{0}),0\leq cg(n)<f(n)

および

\lim_{n\to\infty}\frac{g(n)}{f(n)}=0

を満たすことと同値である。

　この定理より直ちに以下の補題が与えられる。

補題

　 $f_{1}(n)\in\Theta(g(n)),f_{2}(n)\in O(g(n))$ について

f_{1}(n)+f_{2}(n)\in\Theta(g(n))。

　同様にして、 $f_{3}(n)\in\Omega(g(n))$ について

f_{1}(n)+f_{3}(n)\in\Theta(g(n))。

証明

　 $f_{2}(n)\in\Theta(g(n))$ のときは自明であるため $f_{2}(n)\not\in\Theta(g(n))$ 、すなわち $f_{2}(n)\in o(g(n))$ の場合を示す。 $\frac{f_{1}(n)+f_{2}(n)}{g(n)}$ の $n\to\infty$ について考えると

\lim_{n\to\infty}\frac{f_{1}(n)+f_{2}(n)}{g(n)}=\lim_{n\to\infty}\frac{f_{1}(n)}{g(n)}

となり、0でない有限の値をとる。つまり、 $f_{1}(n)+f_{2}(n)\in\Theta(g(n))$ である。また、 $f_{3}(n)$ についても同様である。
　よって、命題は証明された。

　与えたこれらの漸近記法は厳密には集合であるが、慣習として $f(n)=O(n)$ のように等号で記述することがある。

分割統治法の計算量

　まずは、漸近記法を用いて分割統治法のアルゴリズムについての一般の漸化式を示す。最悪計算量 $T(n)$ のアルゴリズムが

\begin{dcases}T(1)=\Theta(1) & (n=1) \\T(n)=aT\left(\frac{n}{b}\right)+f(n) & (other)\end{dcases}

のような漸化式で記述されるとする。なお、 $a\geq 1,b>1$ で $\frac{n}{b}$ は切り上げもしくは切り捨てを示す。
　この漸化式を解く手法として以下の3つが存在する。

置き換え法(substitution method)
　限界を推定して数学的帰納法により証明をする手法。
再帰木法(recursion-tree method)
　漸化式を木として展開し、各節点を再帰レベルに対する必要な計算量としてその和により限界を与える手法。
マスター法(master method)
　上記の漸化式を解くことにより限界を与える手法。

　以下ではそれぞれを解説していく。

置き換え法

　置き換え法については前述したとおりであるため、簡単な例を示す。簡単のために

\begin{dcases}T(1)=1 & (n=1) \\T(n)=2T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n & (other)\end{dcases}

を解くことを考える。
　 $T(n)=O(n\log{n})$ と推定すれば、ある $n_{0}>0$ が存在して、 $n>n_{0}$ においてある定数 $c>0$ が存在して $T(n)\leq cn\log{n}$ を満たすこととなる。これを漸化式に代入すると

\begin{aligned}T(n)=&2c\left\lfloor\frac{n}{2}\right\rfloor\log{\left\lfloor\frac{n}{2}\right\rfloor}+n \\\leq&cn\log{\frac{n}{2}}+n \\=&cn\log{n}-cn\log{2}+n \\\leq&cn\log{n}。\end{aligned}

　なお、この操作の最後の不等号は $1-c\log{2}\leq 0$ となるように $c$ を選択したこととする。つまり、 $\frac{1}{\log{2}}\leq c$ である。
　次に、 $n_{0}$ を求める。 $n=1$ のときは $T(1)=1$ および $c\log{1}=0$ となるため $T(n)\leq cn\log{n}$ は成り立たない。 $n=2$ のときは $T(2)=4$ および $2c\log{2}>0$ となるため適当な $c$ を選択することにより $T(n)\leq cn\log{n}$ が成り立つ。よって、 $n_{0}=2$ となる。
　以上より、数学的帰納法により $T(n)=O(n\log{n})$ となる。
　次に、 $T(n)$ の下界を偶数 $2n$ と奇数 $2n+1$ に分けて考える。まず、偶数のとき $T(2n)=\Omega(2n\log{2n})$ と推定すれば

\begin{aligned}T(2n)=&2c\left\lfloor\frac{2n}{2}\right\rfloor\log{\left\lfloor\frac{2n}{2}\right\rfloor}+2n \\=&2cn\log{\frac{2n}{2}}+2n \\=&2cn\log{2n}-2cn\log{2}+2n \\\geq&c\cdot 2n\log{2n}。\end{aligned}

　なお、この操作の最後の不等号は $1-c\log{2}\geq 0$ となるように $c$ を選択したこととする。つまり、 $\frac{1}{\log{2}}\geq c$ である。奇数のときは、 $T(2n+1)=\Omega(2n\log{2n})$ と推定すれば

\begin{aligned}T(2n+1)=&2c\left\lfloor\frac{2n+1-1}{2}\right\rfloor\log{\left\lfloor\frac{2n+1-1}{2}\right\rfloor}+2n+1 \\=&2cn\log{\frac{2n}{2}}+2n+1 \\=&2cn\log{2n}-2cn\log{2}+2n+1 \\\geq&2cn\log{2n}-2cn\log{2}+2n \\\geq&c\cdot 2n\log{2n}。\end{aligned}

なお、この操作の最後の不等号は $1-c\log{2}\geq 0$ となるように $c$ を選択したこととする。つまり、 $\frac{1}{\log{2}}\geq c$ である。 $n_{0}$ については $T(n)=O(n\log{n})$ と推定した場合と同様に考えることで $n_{0}=1$ と求まる。
　以上より、数学的帰納法により $T(n)=\Omega(n\log{n})$ となり、 $T(n)=\Theta(n\log{n})$ が得られる。

　このようにして、限界を推定して数学的帰納法を用いることで計算量を求めることができる。

再帰木法

　再帰木法についても前述したとおりである。しかしながら、再帰木法により得られた計算量が $T(n)$ の上界もしくは下界となるとは限らないことに留意する必要がある。あくまでも置き換え法により確かめる場合のよりよい推定を与える手法である。また、推定を与えるだけであるため、ある程度の杜撰さも許される。
　そこで、例として前述した置き換え法により計算量を与えた

\begin{dcases}T(1)=1 & (n=1) \\T(n)=2T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n & (other)\end{dcases}

を再帰木法により推定をする。この漸化式により生成される木の深さは $T(n)$ に対して $\log_{2}{n}$ であるため、これらを直接和をとる。このときの最悪計算量は $n$ が2の冪乗となる場合であるため、 $n=2^{N}$ と置換して考える。これにより、

\begin{aligned}T(n)=&2T(2^{N-1})+2^{N} \\=&2(T(2^{N-2})+2^{N-1})+2^{N} \\=&N2^{N} \\=&n\log_{2}(n)\end{aligned}

が得られ、最悪計算量が $T(n)=\Theta(n\log{n})$ と推定される。そして、これを前述で行ったように置き換え法により整合性を証明すればいい。しかしながら、これは等号により式変形をして与えられているため正確に $T(n)=\Theta(n\log{n})$ となり、置き換え法を用いる必要はない。

マスター法

　マスター法についても前述のとおりであり、それは以下のマスター定理により与えられる。

証明

定理

　最悪計算量 $T(n)$ のアルゴリズムが

\begin{dcases}T(1)=\Theta(1) & (n=1) \\T(n)=aT\left(\frac{n}{b}\right)+f(n) & (other)\end{dcases}

のような漸化式で記述されるとする。なお、 $a\geq 1,b>1$ で $\frac{n}{b}$ は切り上げもしくは切り捨てを示す。このとき、非負の関数 $f(n)$ により以下の分類が与えられる。

$\exist \varepsilon>0,f(n)=O(n^{\log_{b}{a}-\varepsilon})\ \Rightarrow\ T(n)=\Theta(n^{\log_{b}{a}})$
$f(n)=\Theta(n^{\log_{b}{a}})\ \Rightarrow\ T(n)=\Theta(n^{\log_{b}{a}}\log{n})$
$\exist \varepsilon>0,f(n)=\Omega(n^{\log_{b}{a}+\varepsilon}),\exist c<0,\exist n_{0}>0\ s.t.\ \forall n>n_{0},af\left(\frac{n}{b}\right)\leq cf(n)\ \Rightarrow\ T(n)=\Theta(f(n))$

　これをマスター定理(master theorem)という。特に、 $\exist n_{0}>0\ s.t.\ \forall n>n_{0},af\left(\frac{n}{b}\right)\leq cf(n)$ であることを $f(n)$ は正則性を満たすという。

証明

　まず、 $n$ が $b$ の冪乗、すなわち $n=b^{N}$ と表現される場合を示す。これを再帰木として展開すると

\begin{aligned}T(n)=&aT(nb^{-1})+f(n) \\=&a(aT(nb^{-2})+f(nb^{-1}))+f(n) \\=&\Theta(a^{N})+\sum_{k=0}^{N-1}a^{k}f(nb^{-k})\end{aligned}

と与えられるため、これに対して $f(n)$ を代入して $T(n)$ の計算量を与える。また、

a^{N}=(b^{\log_{b}{a}})^{N}=b^{N\log_{b}{a}}=n^{\log_{b}{a}}

となることを用いる。1)について、 $f(n)=O(n^{\log_{b}{a}-\varepsilon})$ とおけば

\begin{aligned}T(n)=&\Theta(a^{N})+\sum_{k=0}^{N-1}a^{k}O((nb^{-k})^{\log_{b}{a}-\varepsilon}) \\=&\Theta(a^{N})+O\left(n^{\log_{b}{a}-\varepsilon}\sum_{k=0}^{N-1}a^{k}(b^{\log_{b}{a}-\varepsilon})^{-k}\right) \\=&\Theta(a^{N})+O\left(n^{\log_{b}{a}-\varepsilon}\sum_{k=0}^{N-1}a^{k}a^{-k}b^{k\varepsilon}\right) \\=&\Theta(a^{N})+O\left(n^{\log_{b}{a}-\varepsilon}\frac{b^{N\varepsilon}-1}{b^{\varepsilon}-1}\right) \\=&\Theta(a^{N})+O(n^{\log_{b}{a}-\varepsilon}n^{\varepsilon}) \\=&\Theta(n^{\log_{b}{a}})+O(n^{\log_{b}{a}}) \\=&\Theta(n^{\log_{b}{a}})。\end{aligned}

　2)について、 $f(n)=\Theta(n^{\log_{b}{a}})$ とおけば

\begin{aligned}T(n)=&\Theta(a^{N})+\sum_{k=0}^{N-1}a^{k}\Theta((nb^{-k})^{\log_{b}{a}}) \\=&\Theta(a^{N})+\Theta\left(n^{\log_{b}{a}}\sum_{k=0}^{N-1}a^{k}(b^{\log_{b}{a}})^{-k}\right) \\=&\Theta(a^{N})+\Theta\left(n^{\log_{b}{a}}\sum_{k=0}^{N-1}a^{k}a^{-k}\right) \\=&\Theta(a^{N})+\Theta\left(n^{\log_{b}{a}}N\right) \\=&\Theta(n^{\log_{b}{a}})+\Theta(n^{\log_{b}{a}}\log_{b}{n}) \\=&\Theta(n^{\log_{b}{a}}\log_{b}{n})。\end{aligned}

　なお、最後の行に関しては $n\geq b$ で $n^{\log_{b}{a}}\leq n^{\log_{b}{a}}\log_{b}{n}$ となることを用いた。3)について、

g(n)=\sum_{k=0}^{N-1}a^{k}f(nb^{-k})

とすれば $a^{k}f(nb^{-k})$ は非負であるため $g(n)=\Omega(f(n))$ である。正則性より十分に大きな $n$ で $f(nb^{-1})\leq \frac{c}{a}f(n)$ が成り立ち、さらに $f(nb^{-2})\leq \frac{c}{a}f(nb^{-1})$ が成り立つことから $f(nb^{-2})\leq \left(\frac{c}{a}\right)^{2}f(n)$ であり、 $n$ は $n_{0}$ よりも十分に大きいものと仮定してこれを繰り返すことにより

a^{k}f(nb^{-k})\leq c^{k}f(n)

が成り立つ。これを満たさないのは $nb^{-k}\leq n_{0}=O(1)$ を満たす高々定数個であり、 $a^{k}f(nb^{-k})=O(1)$ である。その個数を $M$ としたとき

\sum_{k=N-M}^{N-1}a^{k}f(nb^{-k})=MO(1)=O(1)

であり、

\begin{aligned}g(n)\leq&\sum_{k=0}^{N-1}c^{k}f(n)+\sum_{k=N-M}^{N-1}a^{k}f(nb^{-k}) \\\leq&f(n)\sum_{k=0}^{\infty}c^{k}+O(1) \\=&\frac{f(n)}{1-c}+O(1) \\=&O(f(n))\end{aligned}

となり、 $g(n)=\Theta(f(n))$ が成り立つ。これを用いることで $f(n)=\Omega(n^{\log_{b}{a}+\varepsilon})$ より $T(n)$ は

T(n)=\Theta(n^{\log_{b}{a}})+\Theta(f(n))=\Theta(f(n))。

　なお、これは十分に大きな $n$ である $c_{1}>0,c_{2}>0$ を用いて $c_{1}n^{\log_{b}{a}}\leq c_{1}n^{\log_{b}{a}+\varepsilon}\leq f(n)\leq c_{2}n^{\log_{b}{a}+\varepsilon}$ となることを用いた。
　次に、 $n=b^{N}$ とあらわされる $n$ だけではなくすべての $n$ 、すなわち

T(n)=aT\left(\left\lfloor\frac{n}{b}\right\rfloor\right)+f(n)\ or\ T(n)=aT\left(\left\lceil\frac{n}{b}\right\rceil\right)+f(n)

の場合について示す。まずは $\frac{n}{b}$ が切り上げの場合について、再帰木を生成するにあたって

n_{k}=\begin{dcases}n & (k=0) \\\left\lceil\frac{n_{k-1}}{b}\right\rceil & (other)\end{dcases}

と記述する。また、 $\lceil x\rceil\leq x+1$ より上記漸化式を繰り返し適用することで

\begin{aligned}n_{0}\leq&n \\n_{1}\leq&\frac{n}{b}+1 \\n_{2}\leq&\frac{n}{b^{2}}+\frac{1}{b}+1 \\&\vdots\end{aligned}

となることから $n_{k}$ については

n_{k}\leq\frac{n}{b^{k}}+\sum_{i=0}^{k-1}\frac{1}{b^{i}}<\frac{n}{b^{k}}+\sum_{i=0}^{\infty}\frac{1}{b^{i}}=\frac{n}{b^{k}}+\frac{b}{b-1}

が成り立つ。再帰の深さを $\lfloor\log_{b}{n}\rfloor$ と推定すると、 $\lfloor x\rfloor>x-1$ より $k=\lfloor\log_{b}{n}\rfloor$ のときは

\begin{aligned}n_{\lfloor\log_{b}{n}\rfloor}<&\frac{n}{b^{\lfloor\log_{b}{n}\rfloor}}+\frac{b}{b-1} \\<&\frac{n}{b^{\log_{b}{n}-1}}+\frac{b}{b-1} \\=&b+\frac{b}{b-1} \\=&O(1)\end{aligned}

となり、高々定数となるため再帰の深さは $\lfloor\log_{b}{n}\rfloor$ である。これより、 $n=b^{N}$ のときは再帰の深さが $N$ であったことに対応して、再帰木として $T(n)$ を展開すると

T(n)=\Theta(a^{\log_{b}{n}})+\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}f(n_{k})=\Theta(n^{\log_{b}{a}})+\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}f(n_{k})

となるため、 $n=b^{N}$ の場合と同じ要領で証明をする。3)について、

g(n)=\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}f(n_{k})

として、正則性より十分に大きな $n$ で $a^{k}f(n_{k})\leq c^{k}f(n)$ が成り立つため $n=b^{N}$ のときと同様にして示される。2)について、 $f(n)=O(n^{\log_{b}{a}})$ よりある定数 $c>0$ が存在して

\begin{aligned}f(n_{k})\leq&cn_{k}^{\log_{b}{a}} \\<&c\left(\frac{n}{b^{k}}+\frac{b}{b-1}\right)^{\log_{b}{a}} \\=&c\left(\frac{n}{b^{k}}\left(1+\frac{b^{k}}{n}\cdot\frac{b}{b-1}\right)\right)^{\log_{b}{a}} \\=&c\left(\frac{n^{\log_{b}{a}}}{a^{k}}\right)\left(1+\frac{b^{k}}{n}\cdot\frac{b}{b-1}\right)^{\log_{b}{a}}\end{aligned}

と記述することができ、 $k\leq\lfloor\log_{b}{n}\rfloor$ で

\frac{b^{k}}{n}\leq\frac{b^{\lfloor\log_{b}{n}\rfloor}}{n}\leq\frac{b^{\log_{b}{n}}}{n}=1

となるため

f(n_{k})<c\left(\frac{n^{\log_{b}{a}}}{a^{k}}\right)\left(1+\frac{b}{b-1}\right)^{\log_{b}{a}}。

　このとき、 $\left(1+\frac{b}{b-1}\right)^{\log_{b}{a}}$ は定数であるため $f(n_{k})=O(a^{-k}n^{\log_{b}{a}})$ となる。また、 $\lceil x\rceil\geq x$ となることから

n_{k}\geq\frac{n}{b^{k}}

となることを用いると、 $f(n)=\Omega(n^{\log_{b}{a}})$ よりある定数 $c>0$ が存在して

f(n_{k})\geq cn_{k}^{\log_{b}{a}}\geq c\frac{n^{\log_{b}{a}}}{a^{k}}

となるため $f(n_{k})=\Omega(a^{-k}n^{\log_{b}{a}})$ となり、 $f(n_{k})=\Theta(a^{-k}n^{\log_{b}{a}})$ が得られる。これを $g(n)$ に代入すると、 $n=b^{N}$ の場合と同様にして

\begin{aligned}g(n)=&\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}\Theta(a^{-k}n^{\log_{b}{a}}) \\=&\Theta\left(n^{\log_{b}{a}}\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}1\right) \\=&\Theta(n^{\log_{b}{a}}\log_{b}{n})\end{aligned}

となり、 $g(n)=\Theta(n^{\log_{b}{a}}\log_{b}{n})$ が得られる。つまり、 $T(n)=\Theta(n^{\log_{b}{a}}\log_{b}{n})$ となる。1)について、2)と同様にして $f(n)=O(n^{\log_{b}{a}-\varepsilon})$ よりある定数 $c>0$ が存在して

f(n_{k})\leq cn_{k}^{\log_{b}{a}-\varepsilon}<c\left(\frac{n}{b^{k}}\right)^{\log_{b}{a}-\varepsilon}\left(1+\frac{b}{b-1}\right)^{\log_{b}{a}-\varepsilon}

となり、 $f(n_{k})=O((nb^{-k})^{\log_{b}{a}-\varepsilon})$ となる。これを $g(n)$ に代入すると $n=b^{N}$ の場合と同様にして

\begin{aligned}g(n)\leq&\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}c((nb^{-k})^{\log_{b}{a}-\varepsilon}) \\=&cn^{\log_{b}{a}-\varepsilon}\frac{b^{\lfloor\log_{b}{n}\rfloor\varepsilon}-1}{b^{\varepsilon}-1} \\\leq&cn^{\log_{b}{a}-\varepsilon}\frac{b^{\log_{b}{n}\varepsilon}-1}{b^{\varepsilon}-1} \\\leq&cn^{\log_{b}{a}-\varepsilon}\frac{n^{\varepsilon}-1}{b^{\varepsilon}-1} \\\leq&cn^{\log_{b}{a}-\varepsilon}\frac{n^{\varepsilon}}{b^{\varepsilon}-1} \\<&cn^{\log_{b}{a}}\frac{1}{b^{\varepsilon}-1}\end{aligned}

となり、 $\frac{1}{b^{\varepsilon}-1}$ は定数であることから $g(n)=O(n^{\log_{b}{a}})$ となる。つまり、 $T(n)=\Theta(n^{\log_{b}{a}})$ である。
　切り捨ての場合については切り上げの場合と同様にして示される。
　よって、命題は証明された。

　この定理を適用できない $f(n)$ というのは1)と2)の間、2)と3)の間に存在する関数および正則でない場合である。例えば、

T(n)=2T\left(\frac{n}{2}\right)+n\log{n}

であるときは、

\lim_{n\to\infty}\frac{n^{\log_{b}{a}}}{n\log{n}}=\lim_{n\to\infty}\frac{n}{n\log{n}}=0

より $n\log{n}=\omega(n^{\log_{b}{a}})$ となるため3)が適用可能であると考えられるが、

\lim_{n\to\infty}\frac{n^{\log_{b}{a}+\varepsilon}}{n\log{n}}=\lim_{n\to\infty}\frac{n^{\varepsilon}}{\log{n}}=\infty

となるため $n\log{n}\neq\Omega(n^{\log_{b}{a}+\varepsilon})$ であり、この漸化式は2)と3)の間に属するため、マスター定理を適用することができない。

練習問題

　最初に挙げた図書の練習問題における事実も割と重要であると思ったため解く。ページとしては87Pの下部にある。
　まずは以下の補題を示す。

補題

　 $a,b\in{\mathbb Z}$ と $x\in{\mathbb R}$ について

\left\lceil\frac{\lceil x/a\rceil}{b}\right\rceil=\left\lceil\frac{x}{ab}\right\rceil,\ \ \ \left\lfloor\frac{\lfloor x/a\rfloor}{b}\right\rfloor=\left\lfloor\frac{x}{ab}\right\rfloor

が成り立つ。

そのうち天井関数と床関数を別の記事で扱うため、そのときにこれは削除する。

証明

　まずは天井関数に対してを示す。天井関数の不等式について

\left\lceil\frac{x}{a}\right\rceil-1<\frac{x}{a}\leq\left\lceil\frac{x}{a}\right\rceil \ \Rightarrow\ \frac{\lceil x/a\rceil-1}{b}<\frac{x}{ab}\leq\frac{\lceil x/a\rceil}{b}

が成り立つ。ここで、 $c=\lceil\frac{x}{a}\rceil$ を $b$ で割れば、剰余 $0\leq r<b$ と商 $q$ を用いて一意に $c=qb-r$ とあらわされることを用いて

\frac{c-1}{b}<\frac{x}{ab}\leq\frac{c}{b}

とあらわすとする。このとき、

q-1\leq\frac{c-1}{b}<\frac{x}{ab}\leq\frac{c}{b}\leq q

と記述することができるため、

\frac{x}{ab}=\frac{c}{b} \ \Rightarrow\ \left\lceil\frac{x}{ab}\right\rceil=\left\lceil\frac{\lceil x/a\rceil}{b}\right\rceil。

　床関数についても同様である。
　よって、命題は証明された。

問題4.6-1

　 $b$ が任意の実数ではなく正の整数であるとき、

n_{k}=\begin{dcases}n & (k=0) \\\left\lceil\frac{n_{k-1}}{b}\right\rceil & (other)\end{dcases}

の $n_{k}$ の簡単で正確な式を求めよ。

解答

　仮定より $b$ は正の整数であるため

n_{2}=\left\lceil\frac{\lceil n/b\rceil}{b}\right\rceil=\left\lceil\frac{n}{b^{2}}\right\rceil

が成り立つ。これを逐次適用することで

n_{k}=\left\lceil\frac{n}{b^{k}}\right\rceil

が得られる。

問題4.6-2

　 $k\geq 0$ とする。 $f(n)=\Theta(n^{\log_{b}{a}}\log^{l}{n})$ ならばマスター法の漸化式の解は $T(n)=\Theta(n^{\log_{b}{a}}\log^{l+1}{n})$ と与えられる。 $b$ の冪乗のみに解析を限定してもよい。

解答

　マスター定理の証明と同様にして

T(n)=\Theta(n^{\log_{b}{a}})+\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}f(n_{k}),\ \ \ g(n)=\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}f(n_{k})

と記述するとする。また、漸化式の $\frac{n}{b}$ が切り上げと切り捨てでどちらも同様に証明されるため、切り上げの場合のみを示す。まず、 $f(n_{k})$ について、 $f(n)=O(n^{\log_{b}{a}}\log^{l}{n})$ よりある定数 $c>0$ が存在して

\begin{aligned}f(n_{k})\leq&cn_{k}^{\log_{b}{a}}\log^{l}{n_{k}} \\<&c\left(\frac{n^{\log_{b}{a}}}{a^{k}}\right)\left(1+\frac{b}{b-1}\right)^{\log_{b}{a}}\log^{l}{n_{k}}\end{aligned}

となり、 $f(n_{k})=O(n^{\log_{b}{a}}a^{-k}\log^{l}{n_{k}})$ が得られる。ここで、 $n_{k}$ を除去するために対数部について展開すると

\begin{aligned}\log^{l}{n_{k}}\leq&\log^{l}\left(\frac{n}{b^{k}}\left(1+\frac{b}{b-1}\right)\right) \\=&\left(\log{\frac{n}{b^{k}}}+\log{\left(1+\frac{b}{b-1}\right)}\right)^{l} \\=&\log^{l}{\frac{n}{b^{k}}}+o(\log^{l}{\frac{n}{b^{k}}}) \\=&O(\log^{l}{\frac{n}{b^{k}}})\end{aligned}

となるため、 $f(n_{k})=O(n^{\log_{b}{a}}a^{-k}\log^{l}{nb^{-k}})$ となる。同様にして、 $f(n)=\Omega(n^{\log_{b}{a}}\log^{k}{n})$ よりある定数 $c>0$ が存在して

f(n_{k})\geq cn_{k}^{\log_{b}{a}}\log^{l}{n_{k}}\geq c\frac{n^{\log_{b}{a}}}{a^{k}}\log^{l}{\frac{n}{b^{k}}}

となるため $f(n_{k})=\Omega(n^{\log_{b}{a}}a^{-k}\log^{l}{nb^{-k}})$ が得られ、 $f(n_{k})=\Theta(n^{\log_{b}{a}}a^{-k}\log^{l}{nb^{-k}})$ となる。これを $g(n)$ に代入すると

\begin{aligned}g(n)=&\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}a^{k}\Theta(n^{\log_{b}{a}}a^{-k}\log^{l}{nb^{-k}}) \\=&\Theta\left(n^{\log_{b}{a}}\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}(\log{n}-\log{b^{k}})^{l}\right) \\=&\Theta\left(n^{\log_{b}{a}}\sum_{k=0}^{\lfloor\log_{b}{n}\rfloor-1}(\log^{l}{n}-o(\log^{l}{n}))\right) \\=&\Theta(n^{\log_{b}{a}}\lfloor\log_{b}{n}\rfloor(\log^{l}{n}-o(\log^{l}{n}))) \\=&\Theta(n^{\log_{b}{a}}(\log^{l+1}{n}-o(\log^{l+1}{n}))) \\=&\Theta(n^{\log_{b}{a}}\log^{l+1}{n})\end{aligned}

となり、 $n^{\log_{b}{a}}\leq n^{\log_{b}{a}}\log^{l+1}{n}$ であるため $T(n)=\Theta(n^{\log_{b}{a}}\log^{l+1}{n})$ となる。

問題4.6-3

　マスター定理の3)は次の意味で冗長である。ある定数 $c<1$ に対して正則性 $af\left(\frac{n}{b}\right)\leq cf(n)$ が成り立つならば、 $f(n)=\Omega(n^{\log_{b}{a}+\varepsilon})$ を満たすある定数 $\varepsilon>0$ が存在する。

解答

　正則性よりある定数 $k$ が存在して

a^{k}f(1)\leq c^{k}f(n)=c^{k}f(b^{\log_{b}{n}})

が成り立ち、 $k$ は高々 $\lfloor\log_{b}{n}\rfloor$ であるため

f(n)\geq\left(\frac{a}{c}\right)^{\log_{b}{n}}f(1)=f(1)n^{\log_{b}{\frac{a}{c}}}=f(1)n^{\log_{b}{a}-\log_{b}{c}}。

　仮定より $c<1$ であるため $\log_{b}{c}<0$ であり、 $\varepsilon=-\log_{b}{c}>0$ として $f(n)=\Omega(n^{\log_{b}{a}+\varepsilon})$ が得られる。

おわりに

　今まで何となくの雰囲気でのみ理解していたが、再勉強した。対数の底は2として扱うべきであると思ったが、底の変換公式より底の違いでは対数は定数倍だけ変わり、漸近記法に関して何も影響はないため無視した。
　証明に関しては割と雑に行ったため(というか途中で日々の疲れで力尽きかけながら書いたため)間違っている気もするが、おおよその筋書きは合っていると思うためこれで良しとした。