(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(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.

显然这不是一个证据,但我认为我们可以看到谁赢得了这场比赛.

Answer 2

f(n)比g (n)增长得更快,当且仅当f(e ⁿ)也比g(e ⁿ)增长更快,因为exp严格增加到无穷大(自己证明).

现在 f(e ⁿ)= n ⁿ和g(e ⁿ)= e ⁿ/n,您可以引用已知结果.