这是关于算法的分析:
例如,问题的运行时间是:
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)
。我怎么才能从大师那里得到正确的答案呢?
最佳答案
它们是一样的。对于任何两个碱基a
和b
,Θ(log n) = Θ(log n)
,所以我们通常根本不提碱基,只说Θ(log n)
。
这是因为log n = (1 / log a) * log n
,所以它们的差别是一个系数1 / log a
,相对于n
,这个系数是常数。