这是关于算法的分析: 比方说，一个问题的运行时间是:
T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1}
现在，这是 THETA(log base3 n)
但是，如果我使用 Master Method，我将评估为 THETA(log base2 n)，使用案例 II
我应该如何从 master 方法中得到正确的答案？
最佳答案
它们是一样的。对于任意两个碱基 a和 b , Θ(log<sub>a</sub> n) = Θ(log<sub>b</sub> n) ，所以我们通常根本不提基数，只说 Θ(log n) .
这是因为log<sub>a</sub> n = (1 / log<sub>b</sub> a) * log<sub>b</sub> n , 所以它们相差 1 / log<sub>b</sub> a这是关于 n 的常数.
关于algorithm - 主方法 - 分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12926620/