n^1.001和n*log n / log 2的时间复杂度哪个更高？

Question

这个问题让我很困惑，希望能在StackOverflow这里得到答案。该问题询问：

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

换句话说，nlogn增长比n^1.001快吗？

我对这个问题感到困惑。我将n^1.001和log n（因为n在等式的两边都有）进行了绘图，绘制了大约10^32左右的图形，然而，即使到那里，n^0.001也没有达到2，而log n要大得多。然而，我不知道哪个增长函数更大，我也无法证明它们。但我想，随着指数大于1，最终n^1.001会加速增长并开始比nlogn增长得快。

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

- Jacqlyn

---

对于所有的 ε > 0，当 n 足够大时，有 n^(1+ε) > nlog(n)。 - msgambel

我想n ^ .001需要很长时间才能达到2，但n ^ 1.001可能需要更少的时间。那是打字错误吗？ - IllusiveBrian

请查看常见函数的阶。“通常情况下，增长较慢的函数排在前面”- 无论如何，这是一个方便的指南。 - user2864740

考虑到当 n > 10 时，n^(1/2) > log(n)，当 n > 100 时，n^(1/4) > log(n)，当 n > 10000 时，n^(1/8) > log(n)，等等。很容易推断出对于所有 ε > 0 和足够大的 n，都有 n^ε > log(n)。 - msgambel

@Namfuak 我有点困惑，不知道该如何表达问题的其余部分。这明显是一个逻辑错误。 - Jacqlyn

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)。希望这可以帮到您！

- msgambel