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

アルゴリズム設計マニュアル 上を読み返した。 漸近計算量の見積もりを素早くできるようにマスター定理ついて整理してイメージを持てるようにしたくなった。

少し前に計算理論の基礎なども読んでいたので計算量について整理する。 見積もりについてのまとめ入門記事も読んだ。 あいかわらず、けんちょんさん(@drken)の記事は勉強になってありがたい。

計算量について

計算を数理的に評価するためには、計算を数理的に表現しないとならない。 こういった数理的な計算の表現を計算模型と呼ぶ。 有名なあたりで具体例を挙げるとラムダ計算とか\( \Pi \) 計算とかチューリングマシンとか。

で、オートマトンやチューリングマシンやレジスタ計算機のように計算システムの数理モデルを特に抽象機械と呼ぶ。 ちなみにチューリングマシンよりも言語の認識能力が劣るものをオートマトンと呼ぶことが多いらしい(wikipediaさん)

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

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

要するに、無限の操作を一瞬で行うことは出来ないことで普通の計算機の特徴を押さえつつ、記憶容量を無限にしてメモリ不足からくる評価の複雑さを避けたモデルになっている。 著書でもさらっと一般にRAMモデルが使われると出てくる。ここでも断らない限りRAMモデルを前提に書く。

時間計算量は一般にRAM上でアルゴリズムを実行した時に掛かる時間を表す。

入力により計算時間は変わるため最善・期待・最悪時間計算量といったように色々な評価がありえる。 期待はサイズ(n)の入力値集合全体に対する期待値を指す。 通常は評価が簡単で重要性も大きな最悪時間計算量を指す。

データ構造の評価の場合には最悪時間計算量の他に償却解析が行われることが多い。 償却解析はある種の期待計算量みたいなもの。複数回の操作に対する期待値を扱う。 データ構造はアルゴリズム内部で利用されるため一回の操作に対する最悪計算量よりも全体としてのコストに着目するとより有用になることがある。 純粋関数型データ構造で触れられている。 またオンラインアルゴリズムとストリームアルゴリズムでも評価モデルの関連で紹介されている。

ここまでアルゴリズムの複雑さを時間から書いてきた。他にはメモリ消費で評価する空間計算量がある。

アルゴリズムの評価と離れるが計算複雑性理論ではアルゴリズムより言語の判定( \( \fallingdotseq \) 問題)の複雑さを扱う。 それらは計算モデルに決定性チューリングマシンや非決定性チューリングマシンを主に利用するものが多い。 計算モデルも特殊な回路計算量も登場する。 \( P \neq NP \) 予想の解決に期待されているらしい(計算理論の基礎; 2000年発行)。 いろいろあるものだ。

計算量の評価

計算量を具体的に見積もるのは難しく有益じゃないことも多い。なので漸近的な挙動を扱う。 いわゆるビッグ-O記法というやつだ。ランダウすごいなー何でもやってるなーって思ったけどレフ・ランダウではないらしい。

漸近記法

ここでは著書で使っている記法で説明する。

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

ビッグオー記法の右辺は関数の集合なので、私は \( f(n) \in O(g(n)) \) とかの方がいい記法だと思っている。 上界かつ下界の\( \Theta(g(n)) \) はタイトな限界(asynmptotic tight bound)とも呼ぶ。

支配関係

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

\[ f(n) \neq \Theta(g(n)) \cap f(n) = O(g(n)) \]

計算量の見積もり

入れ子のループの見積もりとか別に困らない。再帰の見積もりが大事。

分割統治法によるアルゴリズムでは計算量が下のように漸化式で表現されることがある。 ここから漸近的な計算量を見積もりたい。(陽表式にしたい)

\[ \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)

マスター定理の使い方が今回の2つめの主題になる。

再帰木法(Recursion Tree Method)

その前に簡単な再帰木法を説明する。これは次の様な特殊系などを扱う。 適用可能な範囲がわからないけど再帰呼び出しをツリーとして捉えている。

\[ \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} \] \[ \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) \) は正則関数が要求される。

\[ \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 \) と\( 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 \) より分割された結果のマージに掛かるコスト(\( f(n) \) )が小さいと、分割の効果が支配的になる。 当然、分割で小さくなる割合(\( b \) )より問題数が増える割合(\( a \) )が大きければ重くなるし逆もそう。 そういう読み方が出来れば残りの2つも想像がつく。

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

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

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

\[ \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

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

comments powered by Disqus