algorithm - (log(n))^log(n) 和 n/log(n)，哪个更快？

Question

f(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))?

Answer 1

取双方的log:

log(f(n)) = log(log n) * log n

log(g(n)) = log(n) - log(log(n)) = log(n)(1 - log(log(n))/log(n))

显然 log(log(n)) 支配 (1 - log(log(n))/log(n))，所以 g 是 O(f)。 f 不是 O(g)。由于是家庭作业，您可能需要填写详细信息。

通过大量尝试也很容易知道答案应该是什么。 1024 是 2^10，所以取 n=1024:

f(n) = 10^10

g(n) = 1024/10。

显然这不是证据，但我认为我们可以看到谁赢得了这场比赛。