math - 带有 log (n) 和指数的 Big Oh

Question

所以我有一些给定的功能，需要为他们喜欢 Big Oh（我做到了）。

1. n log(n) = O(n log(n))
2. n^2 = O(n^2)
3. n log(n^2) = O(n log(n))
4. n log(n)^2 = O(n^3)
5. n = O(n)

log 是自然对数。

我很确定 1,2,5 是正确的。对于 3，我在这里的某个地方找到了一个解决方案：n log(n^2) = 2 n log (n) => O (n log n) 但我完全不确定 4)。n^3 肯定大于 n*log(n^2) 但它是它的哦？我的另一个猜测是 O(n^2)。

其他几件事：

• n^2 * 对数（n）
• n^2 * log(n)^2 那会是什么？

如果有人可以解释它，如果它是错误的，那就太好了。谢谢！

Answer 1

请记住，big-O 提供了函数的渐近上界，因此 O(n) 的任何函数也是 O(n log n)、O(n ² )、O(n!) 等。因为 log n = O(n)，我们有 n log ² n = O(n ³ )。n log ² n = O(n log ² n) 和 n log ² n = O(n ² ) 也是这种情况。事实上，对于任何 ε > 0，n log ² n = O(n ^{1 + ε} )，因为对于任何 ε > 0，log ^k n = O(n ^ε )。

函数 n ² log n 和 n ² log ² n 不能像其他一些函数那样简化。O(n ^k log ^r n) 形式的运行时并不少见。事实上，有很多算法的运行时间为 O(n ² log n) 和 O(n ² log ² n)，而这些运行时间通常是这样的。例如，Karger-Stein 算法的每次迭代都需要时间 O(n ² log n)，因为这个运行时间来自应用于递归的主定理

T(n) = 2T(n / √2) + O(n ² )

希望这可以帮助！