algorithm - 主方法 - 分析

Question

这是关于算法分析：比如说，一个问题的运行时间是：

T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1}

现在，这是THETA(log base3 n)

但是，如果我使用主方法，我评估为THETA(log base2 n)，使用案例 II

我应该如何从主方法中得到正确的答案？

Answer 1

他们是一样的。对于任意两个基数a和b，所以我们通常根本不提基数，只说。Θ(loga n) = Θ(logb n)Θ(log n)

这是因为，所以它们的不同之处在于 是恒定的。loga n = (1 / logb a) * logb n1 / logb an