algorithm - 主定理 : comparing two versions of the theorem

Question

我一般看过两个版本的大师定理。

版本 1:

(来自 Tim Roughgarden's course)

对于形式的递归关系，

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

第二个版本，因为它对 f(n) 没有约束。

如您所见，在第一个版本中，您的 f(n) 只能是特定形式，第二种情况下 f(n) 是任何函数，因此您可以解决递归问题，例如 T(n) = 2 T(n/2) + nlog(n) + n^2 * sin(n)