algorithm - 具有常数的主定理

Question

这个公式是主定理的案例 2

T(n) = 2 * T(n/2) + 3

a = 2; b = 2; (f(n) = 3^1) ?

所以 logba = 1 和 c = 1 在这种情况下是主定理情况 2 吗？还是我应该忽略常数 3。

Answer 1

这是案例 1公式，因为：

log_b(a) = 1
f(n) = 3,
3 is in O(1)=O(n^0) -> c = 0 < 1 = log_b(a)

所以，公式在Theta(n^(log_b(a)) = Theta(n)

这不是案例 2，因为案例 2 需要f(n)=3在Theta(n^(log_b(a)) = Theta(n)，但f(n)=3不在Theta(n)