algorithm - マスター定理: 2 つのバージョンの定理を比較する

Question

私は通常、マスター定理の 2 つのバージョンを見てきました。

バージョン 1:

(ティム・ラフガーデンのコースより)

フォームの再帰関係については、

T(n) <= aT(n/b)+O(n^d)
where a >= 1, b > 1, and d >= 0

3つのケースがあり、

case 1: if a=b^d, then T(n) = O(n^dlog(n))
case 2: if a<b^d, then T(n) = O(n^d)
case 3: if a>b^d, then T(n) = O(n^logb(a))

バージョン 2:

( CLRSより)

フォームの再帰関係については、

T(n) = aT(n/b)+f(n)
where a>=1 and b>1 (both constants)

3 つのケースがあります。

case 1: if f(n) = O(n^logb(a-ε) for some ε > 0, then T(n) = Θ(n^logb(a))
case 2: if f(n) = Θ(n^logb(a)), then T(n) = Θ(logn*n^logb(a))
case 3: if f(n) = Ω(n^logb(a+ε)) for some ε > 0, and if af(n/b)<=cf(n) for some 
constant c<1 and all sufficiently large n,then T(n) = Θ(f(n))

質問: どちらのバージョンを優先すべきですか? その理由は?

Answer 1

に制約がないため、2 番目のバージョンf(n)。

ご覧のとおり、最初のバージョンでは f(n) は特定の形式でのみ使用できますが、2 番目のケースでは f(n) は任意の関数であるため、次のような繰り返しを解決できます。T(n) = 2 T(n/2) + nlog(n) + n^2 * sin(n)