1

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

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

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

4

2 回答 2

1

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

日志a x= 日志b x/日志b a

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

于 2013-07-04T11:12:30.153 回答
0

回想一下大欧米茄的定义：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).

于 2013-07-04T10:59:09.127 回答