algorithm - 通过转换对数基数证明递归的下限

Question

“算法简介”中有一个问题说：（4.4-6）

通过诉诸递归树，论证T(n) = T(n/3) + T(2*n/3) + cn
其中c为常数的递归的解是 Ω(n log _{2 n)。}

我使用递归树，最后得到. 我不知道下一步要表明这一点，我也用谷歌搜索了它，不知何故我觉得答案有问题，因为他们说那时（但不大于）。T(N) >= n log₃n
T(N) >= n log₂n
T(N) >= n log₃nT(N) >= n log₂nlog₃nlog₂n

score 1 · Accepted Answer

在渐近界中，对数的底数无关紧要，因为它只是一个恒定的变化。这是由于对数底数的变化。

日志_a x= 日志_b x/日志_b a

这就是为什么人们不在渐近界写底的原因。

score 0 · Accepted Answer

回想一下大欧米茄的定义：f(n)在中Omega(g(n))，如果f在下面是g渐近的。或者，如果你更喜欢数学：

大欧米茄的定义

让我们定义f(n) = n * log_3(n)和g(n) = n * log_2(n)。

现在，如果我们可以找到一个常数，c那么f(n) > c * g(n)我们已经证明f(n)了Omega(g(n))。

    log_3(n) = log_2(n) / log_2(3)
    log_2(3) ~= 1.585 < 2
=>  log_3(n) > 2 * log_2(n)
=>  n * log_3(n) > 2 * n * log_2(n)
=>  f(n) > c * g(n)

对于我们选择的值c = 2（当然，您可以选择任何其他值，只要c > log_2(3).

2 回答 2