読書: 計算量とマスター定理

Posted on 4 mins read

読書: 計算量とマスター定理

マスター定理の意味を押さえたい。周辺を整理して押さえた上で漸近計算量の見積もりをやれるようになりたい。 マスター定理は分割統治法による時間計算量を求める定理です。分割統治法では下のような漸化式が出てくることがしばしばある。

T(n)={aT(n/b)+f(n)if n>n0cif otherwisefor ∃c,n0,a≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned}

ここでは f(n) f(n) は正則関数が想定されています。 この式に対して時間計算量T(n) T(n)の陽関数を求めるために使われる定理がマスター定理です。

マスター定理では適用に分岐があります。確認するのはlog⁡ba \log_baとf(n) f(n)の関係。

if f(n)=O(nlog⁡ba−ϵ) for ∃ϵ>0, then T(n)=Θ(nlog⁡ba)if f(n)=Θ(nlog⁡ba), then T(n)=Θ(nlog⁡balog⁡n)if f(n)=Ω(nlog⁡ba+ϵ) for ∃ϵ>0 and af(n/b)<cf(n) for ∃c<1, then T(n)=Ω(f(n)) \begin{alignedat}{2} \text{if }&f(n) = O(n^{\log_ba - \epsilon}) \text{ for } \exists \epsilon > 0 & \text{, then } T(n) = \Theta(n^{\log_ba}) \\ \text{if }&f(n) = \Theta(n^{\log_ba}) & \text{, then } T(n) = \Theta(n^{\log_ba}\log{n}) \\ \text{if }&f(n) = \Omega(n^{\log_ba + \epsilon}) \text{ for } \exists \epsilon > 0 \text{ and } af(n/b) \lt cf(n) \text{ for } \exists c \lt 1 & \text{, then } T(n) = \Omega(f(n)) \end{alignedat}

まとめておきたくなったのはアルゴリズム設計マニュアル 上を読み返した時に忘れそうだとおもったからです。 参考にした資料は下の3つ。

まずは計算量の周辺の復習をします。

計算量の準備: 計算模型との関係

計算を数理的に評価するために数理的に表現しないとならない。こういった数理的な表現を計算模型と呼びます。 有名なあたりで具体例を挙げるとラムダ計算とかΠ \Pi計算とかチューリングマシンとか。とくにオートマトンやチューリングマシンやレジスタ計算機のような計算システムを経由した数理モデルを特に抽象機械と呼びます。

ちなみにチューリングマシンよりも言語の認識能力が劣るものをオートマトンと呼ぶことが多いらしいです(wikipediaさん)。

抽象機械は問題やアルゴリズムの複雑さの評価に利用されることが多いです。シングルスレッドの普通のアルゴリズムの評価にはRandom Access Machineモデル(RAM)がよく使われる。RAMは下のような特徴を備えています。

  • 各単純操作は1ステップで実行される
  • ループやサブルーチンは単純操作ではない
  • メモリアクセスは1ステップで一回でメモリ不足は起きない

これは、現実的で数学的な道具としても扱いやすい特徴を持っています。

  • 現実的パート担当: 無限の操作を一瞬で行うことは出来ない
  • 数学的な扱いやすさパート担当: 記憶容量が無限なのでメモリ不足が起きない

著書でもさらっと一般にRAMモデルが使われると出てきます。

計算量の説明: 主に時間計算量

アルゴリズムの時間計算量は一般にRAM上で実行した時にかかる時間を指します。問題の時間計算量は解決するアルゴリズムの限界に対応しています。 入力により計算時間は変わるため、最善・期待・最悪時間計算量といったように統計的な評価を行います。さらに値の入力サイズを独立変数として漸近的に評価します。 ふつう計算量と書いたときは、評価しやすく重要な最悪時間計算量を意味します。

データ構造の場合はアルゴリズム内で多くの操作が出てくるため、一つの操作に対する最悪時間計算量よりも連続した操作での期待値を評価することもあるようです。 償却解析と呼ばれるものもあるようです。償却解析については純粋関数型データ構造で少し出てきました。 またオンラインアルゴリズムとストリームアルゴリズムでも評価モデルの節で紹介されています。

時間計算量のほかにメモリ消費に対応する空間計算量や計算回路を作った場合の回路の大きさで評価する回路計算量というのもあります。

計算量の評価

計算量を具体的に見積もるのは難しく得るものも少ないため、入力値の大きさに対してどのように時間が増えていくか? という漸近的な挙動を評価します。 いわゆるビッグ-O記法というやつです。

漸近記法

ここでは自分が読んだ著書で使っていた記法で説明します。

記法 概要 定義
f(n)=O(g(n)) f(n) = O(g(n)) g(n) g(n) は f(n) f(n)の上界 ∃c,∃n0,∀n>n0,f(n)≤cg(n) \exists c,\exists n_0, \forall n > n_0, f(n) \le cg(n)
f(n)=Ω(g(n)) f(n) = \Omega(g(n)) g(n) g(n) は f(n) f(n)の下界 ∃c>0,∃n0,∀n>n0,f(n)≥cg(n) \exists c > 0,\exists n_0, \forall n > n_0, f(n) \ge cg(n)
f(n)=Θ(g(n)) f(n) = \Theta(g(n)) g(n) g(n) は f(n) f(n)の上界かつ下界 f(n)=O(g(n))∩f(n)=Ω(g(n)) f(n) = O(g(n)) \cap f(n) = \Omega(g(n))

ビッグオー記法の右辺は関数の集合なので、私は f(n)∈O(g(n)) f(n) \in O(g(n)) とかの方がいい記法だと思いました。(単に演算子の表記の話です。) 上界かつ下界のΘ(g(n)) \Theta(g(n))はタイトな限界(asynmptotic tight bound)とも呼びます。

支配関係

ビッグオー記法は対象を含めば良いだけなので実は表現として広いです。その階層関係を表すのに次の記法が使われます。

以下を満たすときf fはg gに支配(dominate)されるといい、 f≪g f \ll gやf(n)=o(g(n)) f(n) = o(g(n))と書きます。 後ろの書き方を スモール-O記法 と呼びます。

f(n)≠Θ(g(n))∩f(n)=O(g(n)) f(n) \neq \Theta(g(n)) \cap f(n) = O(g(n))

計算量の見積もり

入れ子のループの見積もりは単に掛け算すればよいので困りません。再帰アルゴリズムの計算量の見積もりが大変です。 最初にも書きましたがマスター定理はその見積もりに使います。分割統治法によるアルゴリズムでは計算量が下のように漸化式で表現されることがあります。

T(n)={aT(n/b)+f(n)if n>n0cif otherwisefor ∃c,n0,a≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned}

有名なアプローチが3つあるようです。

  • 再帰木法(Recursion Tree Method)
  • 置き換え法(Substitution Method)
  • 分類法・マスター定理(Master Theorem Method)

再帰木法(Recursion Tree Method)

最初に再帰木法です。これは次の様な特殊系などを扱います。

T(n)={aT(n/a)+O(n)if n>n0cif otherwisefor ∃c,n0≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/a) + O(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c, n_0 \ge 1, b \gt 1 \end{aligned}

適用可能な範囲がわからないけど再帰呼び出し関係をツリーとして捉えます。 下のように式を変形していけば導出できました。

T(n)=bT(n/b)+O(n)=b(bT(n/b2)+O(n/b))+O(n)=b2T(n/b2)+bO(n/b)+O(n)=b2T(n/b2)+2O(n)=blog⁡b(n−n0)T(n0)+log⁡b(n−n0)O(n)=cblog⁡b(n−n0)+log⁡bnO(n)=O(nlog⁡bn) \begin{aligned} T(n) & = bT(n/b) + O(n) \\ & = b\big(bT(n/b^2) + O(n/b) \big) + O(n) \\ & = b^2T(n/b^2) + bO(n/b) + O(n) \\ & = b^2T(n/b^2) + 2O(n) \\ & = b^{\log_b(n-n_0)}T(n_0) + \log_b(n-n_0)O(n) \\ & = cb^{\log_b(n-n_0)} + \log_bnO(n) \\ & = O(n\log_bn) \end{aligned}

置き換え法(Substitution Method)

良い説明を見つけられなかったのですが不等式で押さえて数学的帰納法で証明するアプローチらしいです。

分類法・マスター定理(Master Theorem Method)

マスター定理についてです、改めて漸化式を載せます。

ここで f(n) f(n) は正則関数が要求されています。

T(n)={aT(n/b)+f(n)if n>n0cif otherwisefor ∃c,n0,a≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned}

マスター定理では3つに分岐します。 注目するのはlog⁡ba \log_baとf(n) f(n)の関係です。

if f(n)=O(nlog⁡ba−ϵ) for ∃ϵ>0, then T(n)=Θ(nlog⁡ba)if f(n)=Θ(nlog⁡ba), then T(n)=Θ(nlog⁡balog⁡n)if f(n)=Ω(nlog⁡ba+ϵ) for ∃ϵ>0 and af(n/b)<cf(n) for ∃c<1, then T(n)=Ω(f(n)) \begin{alignedat}{2} \text{if }&f(n) = O(n^{\log_ba - \epsilon}) \text{ for } \exists \epsilon > 0 & \text{, then } T(n) = \Theta(n^{\log_ba}) \\ \text{if }&f(n) = \Theta(n^{\log_ba}) & \text{, then } T(n) = \Theta(n^{\log_ba}\log{n}) \\ \text{if }&f(n) = \Omega(n^{\log_ba + \epsilon}) \text{ for } \exists \epsilon > 0 \text{ and } af(n/b) \lt cf(n) \text{ for } \exists c \lt 1 & \text{, then } T(n) = \Omega(f(n)) \end{alignedat}

この分岐の意味は、分割して小さくなる計算を行い集める操作の計算量 log⁡ba \log_ba に対して統括するオーバーヘッドの計算コスト(f(n) f(n))が十分小さいと分割して集める計算が支配的になると読めます。

分割で小さくなる効果(1/b 1/b)より問題数が増える効果(a a)が大きくても小さくても関係ありません。 この関係に対してf(n) f(n)はその項に対して小さいので常に無視できます。 残りの2つの分岐は、拮抗する場合と統合のオーバーヘッドが支配的な場合です。1つ目の分岐について導出してみます。やってないけど他の2つも同じように展開すれば良いはず。

T(n)=aT(n/b)+O(nlogba−ϵ)=a(aT(n/b2)+O(nlogba−ϵ))+O(nlogba−ϵ)=a2T(n/b2)+aO((n/b)logba−ϵ)+O(nlogba−ϵ)=a2T(n/b2)+aO((nlogba−ϵ∗(1/b)logba−ϵ)+O(nlogba−ϵ)=a2T(n/b2)+(aO(b−logba+ϵ)+1)O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+(1+aO(b−logba+ϵ)+⋯+alog⁡b(n−n0)−1O(b−logba+ϵ)log⁡b(n−n0)−1))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(1+ab−logba+ϵ+⋯+(ab−logba+ϵ)log⁡b(n−n0)−1))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(((ab−logba+ϵ)log⁡b(n−n0)−1−1)/((ab−logba+ϵ)−1))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O((ab−logba+ϵ)log⁡b(n−n0)−1)O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(alog⁡b(n−n0)−1b(−logba+ϵ)×(log⁡b(n−n0)−1)))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(nlog⁡bab(−logba+ϵ)×(log⁡b(n−n0)−1)))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(nlog⁡ban(−logba+ϵ))O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(nϵ)O(nlogba−ϵ)=alog⁡b(n−n0)T(n0)+O(nlogba)=calog⁡b(n−n0)+O(nlogba)=cnlog⁡ba+O(nlogba)=Θ(nlog⁡ba)+O(nlogba)=Θ(nlog⁡ba) \begin{aligned} T(n) & = aT(n/b) + O(n^{log_ba - \epsilon}) \\ & = a\big(aT(n/b^2) + O(n^{log_ba - \epsilon}) \big) + O(n^{log_ba - \epsilon}) \\ & = a^2T(n/b^2) + aO((n/b)^{log_ba - \epsilon}) + O(n^{log_ba - \epsilon}) \\ & = a^2T(n/b^2) + aO((n^{log_ba - \epsilon}*(1/b)^{log_ba - \epsilon}) + O(n^{log_ba - \epsilon}) \\ & = a^2T(n/b^2) + (aO(b^{-log_ba + \epsilon})+1)O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + (1+aO(b^{-log_ba + \epsilon})+ \dots +a^{\log_b(n-n_0)-1}O(b^{-log_ba + \epsilon})^{\log_b(n-n_0)-1}))O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(1+ab^{-log_ba + \epsilon}+ \dots +(ab^{-log_ba + \epsilon})^{\log_b(n-n_0)-1}))O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(((ab^{-log_ba + \epsilon})^{\log_b(n-n_0)-1} - 1) /((ab^{-log_ba + \epsilon})-1))O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O((ab^{-log_ba + \epsilon})^{\log_b(n-n_0)-1})O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(a^{\log_b(n-n_0)-1}b^{(-log_ba + \epsilon) \times (\log_b(n-n_0)-1))})O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(n^{\log_ba}b^{(-log_ba + \epsilon) \times (\log_b(n-n_0)-1))})O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(n^{\log_ba}n^{(-log_ba + \epsilon)})O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(n^{\epsilon})O(n^{log_ba - \epsilon}) \\ & = a^{\log_b(n-n_0)}T(n_0) + O(n^{log_ba}) \\ & = ca^{\log_b(n-n_0)} + O(n^{log_ba}) \\ & = cn^{\log_ba} + O(n^{log_ba}) \\ & = \Theta(n^{\log_ba}) + O(n^{log_ba}) \\ & = \Theta(n^{\log_ba}) \end{aligned}

マスター定理の適用外は2つあるらしい。

  • f(n) f(n) が正則性を満たさない
  • f(n) f(n) が nlogba n^{log_ba}と多項式等価で f(n)=Θ(n) f(n)=\Theta(n)を満たさない

2つめは f(n)=O(nlog⁡n) f(n)=O(n\log{n}) の場合など。マスター定理には含まれないが次の条件を適用できる。

if f(n)=Θ(nlog⁡balog⁡bka) for k>0, then T(n)=Θ(nlog⁡balog⁡k+1a) \begin{alignedat}{2} \text{if }&f(n) = \Theta(n^{\log_ba}\log_b^ka) \text{ for } k > 0 & \text{, then } T(n) = \Theta(n^{\log_ba}\log^{k+1}{a}) \end{alignedat}

ref. proof techniques - Master theorem not applicable? - Computer Science Stack Exchange

マスター定理の適用外について言及してくれていたブログの人はアルゴリズムイントロダクションを読めと書いていた。