这是关于算法的分析:
例如,问题的运行时间是:

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

现在,这是THETA(log base3 n)
但是,如果我使用master方法,我会使用case i i评估到THETA(log base2 n)
我怎么才能从大师那里得到正确的答案呢?

最佳答案

它们是一样的。对于任何两个碱基abΘ(log n) = Θ(log n),所以我们通常根本不提碱基,只说Θ(log n)
这是因为log n = (1 / log a) * log n,所以它们的差别是一个系数1 / log a,相对于n,这个系数是常数。

10-06 05:07
查看更多