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

マスター定理ついて整理して漸近計算量の見積もりを素早くできるようになっておきたい。 まず、計算量について確認する。

きっかけはアルゴリズム設計マニュアル 上を読み返したから。 参考にした資料は下の3つ。

あいかわらず、けんちょんさん(@drken)の記事は勉強になってありがたい。

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

計算を数理的に評価するために数理的に表現しないとならない。

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

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

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

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

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

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

著書でもさらっと一般にRAMモデルが使われると出てくる。ここでも断らない限りRAMモデルを前提に書く。

アルゴリズムの評価と離れるが計算複雑性理論では言語判定( \( \fallingdotseq \) 問題)の複雑さを扱う。 そのときは計算モデルに決定性チューリングマシンや非決定性チューリングマシンを主に利用する。 大きな関心となっている P, NPといった計算クラスの関係が計算模型に対して安定なことと、これらの模型が扱いやすいためとのこと。

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

アルゴリズムの時間計算量は一般にRAM上で実行した時にかかる時間を指す。 問題の時間計算量は解決するアルゴリズムの限界に対応する。

入力により計算時間は変わるため最善・期待・最悪時間計算量といったように統計的な評価を行う。 さらに値の入力サイズを独立変数とした漸近的に評価する。

ふつう計算量と書いたときは評価しやすく重要な最悪時間計算量を意味している。

アルゴリズムや問題ではなくデータ構造の場合、アルゴリズム内で多くの操作が行われる。 そのため一つ一つの操作に対する最悪時間計算量よりも複数操作における期待値が有用になる。 そこで償却解析が行われることもある。償却解析はある種の期待計算量みたいなもので複数操作全体でのコストに着目したもの。

純粋関数型データ構造で触れられている。 またオンラインアルゴリズムとストリームアルゴリズムでも評価モデルの関連で紹介されていた。

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

いろいろあるものだ。

計算量の評価

計算量を具体的に見積もるのは難しく有益じゃないことも多い。なので漸近的な挙動を扱う。 いわゆるビッグ-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