1

所以我有一些给定的功能,需要为他们喜欢 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 那会是什么?

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

4

1 回答 1

2

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

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

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

希望这可以帮助!

于 2013-08-18T19:10:50.850 回答