LifeTimeException@hrk623

This is my breakpoints and stack-trace for my life

分類定理(master theorem)

 世界高校生プログラミング大会IOIも開催されるというので、今回はアルゴリズム解析ネタです。と言っても、昔のノートを引っ張り出してきただけっゲフンゲフン・・・と、とりわけ、再帰プログラムの実行時間の計算に使われる分類定理についてです。

その前に

 アルゴリズム解析の際、表記には実行時間の成長を表す漸近記法を使います。よく知られているのは上界を表すO記法ですが、今回は上下界を表すΘ記法を使いますので、そちらも既に習得されている事を前提とします。(知らなくても特に問題はないかも?)

ではでは、

T(n)= \begin{cases} aT(\frac{n}{b}) + f(n) & \mbox{if } n > n_0 \\c & \mbox{otherwise}\end{cases}\\for\;c,\;n_0,\;a\ge 1,\;b>1\;are\;constants

 再帰プログラムの実行時間は、大抵↑のような形になるので単純な計算で漸近実行時間は出てきません。

そこで

 漸近実行時間の計算には、次のような3つの計算方法があります。

  1. 置き換え法(Substitution Method)
  2. 再帰木法(Recursion Tree Method)
  3. 分類法(Master Theorem Method)

今回は、

 冒頭でも述べたとおり分類定理の紹介です。英語ではMaster Theoremとよばれていて、theoremという言葉には、神という意味のtheoが入っていて、マスターで神様などうたらこうたら・・・。一見難しそうですが使い方さえ覚えれば計算はほとんどありません。強面優男タイプ。

分類定理(Master Theorem)を定義してみる

 実行時間関数が

T(n)= \begin{cases} aT(\frac{n}{b}) + f(n) & \mbox{if } n > n_0 \\c & \mbox{otherwise}\end{cases}\\for\;c,\;n_0,\;a\ge 1,\;b>1\;are\;constants

 の形式をしていて以下のいずれかの条件に当てはまれば、分類定理によって漸近実行時間を単なる代入によって計算できます。

 Let \; d = \log_b a,

  1. if\;f(n) \in O(n^{d-\varepsilon})\ for\; some\; \varepsilon > 0\; then\; T(n) \in \Theta(n^d)
  2. if\; f(n) \in \Theta(n^d)\; then\; T(n) \in \Theta(f(n) \log n)
  3. if\;f(n) \in \Omega(n^{d+\varepsilon})\; for\; some\; \varepsilon > 0\; and \; af(\frac{n}{b}) \le cf(n)\; for\; some\; c < 1 \; then\; T(n) \in \Theta (f(n))
  • ちなみに、2については\Theta(n^d \log n)と書く人もいますが、f(n)\in \Theta(n^d)なので、どちらでも特に問題はないと思います。
  • Case3には追加条件として正則条件(Regularity Condition)があります。ものすごく簡単に言うと、「再帰するたびに計算量が増えちゃだめだよ」って事ですね。

 以上が分類定理を使うための三つの条件です。上のどれにも当てはまらない場合は、分類定理は使えません。

使ってみよう!、の前に・・・

 使い方だけサラッと紹介。分類定理は一見難しいそうに見えて、その計算は至って簡単。手順は完全テンプレート化されています。

  1. a, b, f(n), dをそれぞれ見つける。
  2.  \begin{cases}n^d =\; ?\\f(n) =\; ?\end{cases}を比べ、どのCaseにあたるかを調べる。
  3. Case1かCase2なら終わり。Case3なら正則条件が合うか調べる。

今度こそ使ってみよう

 例題を見てみましょう。

例1: T(n) = 2T(\frac{n}{2}) + \Theta(n)

  a = 2,\; b = 2,\; f(n) = n,\; d = \log_2 2 = 1

  \begin{cases}n^d  = n^1 & = n\\f(n) & = n\end{cases}

 これは、Case2の条件に当てはまるのでT(n)\in \Theta(n \log n)ですね。


例2: T(n) = 3T(\frac{n}{4}) + \sqrt{n}

  a = 3,\; b = 4,\; f(n) = \sqrt{n},\; d = \log_4 3

  \begin{cases}n^d  = n^{\log_4 3} & = n^{0.79...}\\f(n)  = \sqrt{n} & = n^{0.5}\end{cases}

 これは、 \varepsilon \le 0.29をとればCase1の条件に当てはまるのでT(n)\in \Theta(n^{\log_4 3})であると言えます。


例3:T(n) = T(\frac{n}{2}) + 1

 この実行時間関数は二分木探索などでよく見かけますね。

  a = 1,\; b = 2,\; f(n) = 1,\; d = \log_2 1 = 0

  \begin{cases}n^d = n^0 & = 1\\f(n) & = 1\end{cases}

 これは、Case2の条件に当てはまるので T(n)\in \Theta(\log n)です。


例4:T(n) = 2T(\frac{n}{4}) + n

  a = 2,\; b = 4,\; f(n) = n,\; d = \log_4 2 = \frac{1}{2}

  \begin{cases}n^d & = n^{\frac{1}{2}}\\f(n) & = n\end{cases}

  \varepsilon = 0.17 とすれば  f(n) \in \Omega(n^{d+\varepsilon})

 となるので、一見Case3の条件に当てはまってますね。でも焦りは禁物。Case3 には必ず正則条件のチェックをしましょう。

  af(\frac{n}{b}) \le cf(n)\; \exists\; c < 1\\\Rightarrow 2f(\frac{n}{4}) \le cf(n)\\\Rightarrow 2(\frac{n}{4}) \le cn\\\Rightarrow c \ge \frac{1}{2}

 つまり、 \frac{1}{2} \le c < 1になるcを選べばいいわけです。

  c = \frac{3}{4}

 とすれば、心置きなくCase3の条件を満たせるので、 T(n) \in \Theta(n)となりますね。


例5: T(n) = 2T(\frac{n}{2}) + n \log n

  a = 2, b = 2, f(n) = n \log n, d = \log_2 2 = 1

  \begin{cases}n^d = n^1 & = n\\f(n) & = n \log n\end{cases}

 この問題では \varepsilon >0 として  f(n) \in \Omega(n^{1+\varepsilon})を見てみましょう。つまり、

  n \log n \in \Omega(n^{1+\varepsilon})

 が正当かどうかと言うことです。ちょっと計算してみると・・・、

  \Rightarrow \log n \notin \Omega(n^{\varepsilon})

 と言う事でCase3は正則条件を確かめるまでもなく当てはまりませんでした。もちろんCase1もCase2も当てはまらないので、この問題は分類定理では解けない事がわかりますね。ちなみに答えは f(n) \in \Theta(n \log^2 n)だそうです。


結論

  • Master Theoremはほぼ代入のみでΘ記法の計算ができるので便利!
  • でも当てはまらないケースもある!
  • しかも、三つのケースと正則条件は暗記!めんどくさい!
  • 結論として、Master Theoremは名前負け。マスターでも神定理でもなんでもなi・・うわなにをするやめ@#$%^&

余談ですが、

  • ウォータルー大学のコンピュータサイエンスの生徒は、分類定理のが正しい証明も覚えさせられたりします。といっても再帰木を使うだけなのでそんなに難しくないのですが、長いです。・・・長かったです。
  • 分類定理についての日本語版Wikiはないのかな?