主定理与常数

Question

3

这个公式是否属于主定理的第二种情况？

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

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

在这种情况下，logba = 1且c = 1，是否符合主定理的第二种情况？还是应该忽略常数3。

- FoldFence

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这是一个案例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)中。