algorithm - n^1.001 的大 O vs n*log n/log 2？

Question

这个问题让我陷入困境，我希望 StackOverflow 是提出这个问题的正确地点。问题是问

n^1.001 = O(n log n) (log is base 2)

换句话说，n log n 的增长速度是否快于 n^1.001。

在这个问题上我一直在兜圈子。我绘制了 n^1.001 与 log n 的关系图(我取出了 n，因为 n 在等式的两边)。在我的程序崩溃之前，我将它们绘制成大约 10^32 左右，甚至到那里，n^0.001 甚至还没有达到 2，而 log n 更大。然而，我想知道并且无法证明任何一种方式，最终 n^1.001 会开始增长并比 n log n 快得多，因为它的指数大于 1。

这是正确的吗？哪个的增长函数更大？

Answer 1

考虑以下事实:

n^(1/2) > log(n) for n > 10,
n^(1/4) > log(n) for n > 100,
n^(1/8) > log(n) for n > 10000, etc.

对于所有 ε > 0，n 足够大的情况，很容易推断出 n^ε > log(n)。希望对您有所帮助!