我通常看到两个版本的 Master 定理。
版本 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))
问题： 应该支持哪个版本，为什么？