math - 分析奇怪的数学表达式 (logN)^logN 和 n/logN 之间的 BIg O 关系

Question

(logN)^logN 和 n/logN 这两者之间的大 O 关系是什么？以及如何得出关系的证明？

Answer 1

您可以做出的一个初步观察是，如果您记录这两个表达式的日志，您会得到以下结果：

log ((log n) ^{log n} ) = log n log log n

log (n / log n) = log n - log log n

请注意，这些术语中的第一个比第二个增长得更快，所以我们希望得到 n / log n = O((log n) ^{log n} )。

为了证明这一点，我们可以将这些表达式的比率限制为 n 趋于无穷大。如果我们得到 0，那么我们就完成了。我将把它作为一个众所周知的练习留给读者。:-)

希望这可以帮助！

Answer 2

替代x = log n。如果对数以底为底a，则有n = a^x. 现在，

(log n)^(log n) = x^x
n / log n       = a^x / x

当你有 x x > ax ^> a ^x。a > 1

另一方面，当 时x > 1，a ^x > a ^x / x。

结合这两者，你得到 x ^x > a ^x / x。如果你现在换回来，

(log n)^(log n) > n / log n        when log n > a, i.e. when n > a^a 

这证明 n/log n 在 O((log n) ^{log n} ) 中。