常数定理
Master Theorem with constant
这个公式是主定理中的案例2吗
T(n) = 2 * T(n/2) + 3
a = 2; b = 2; (f(n) = 3^1) ?
所以在这种情况下 logba = 1 和 c = 1 是主定理情况 2 吗？
或者我应该忽略常量 3.
这是一个 case 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)
中
这个公式是主定理中的案例2吗
T(n) = 2 * T(n/2) + 3
a = 2; b = 2; (f(n) = 3^1) ?
所以在这种情况下 logba = 1 和 c = 1 是主定理情况 2 吗？ 或者我应该忽略常量 3.
这是一个 case 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)