algorithm - 同一功能的几个大 O 符号

Question

让f(n)= ( (n^2+2n)/n + 1/1000*(n^(3/2)))*log(n)

这个函数的时间复杂度可能是O(n²*log(n)) and O(n^(3/2)*log(n))

这怎么可能？我认为这里的主要术语是n² (*log(n))，因此它应该O(n²*log(n))只是大O符号，时间复杂度度量感觉如此模棱两可

Answer 1

大 O 符号并不那么令人困惑。它定义了算法运行时间的上限，因此，如果O(f(n))是一个有效的上限，则每隔一个O(g(n))这样g(n) > f(n)肯定是有效的，因为如果您的代码将在 less 中运行，那么f(n)肯定会在 less 中运行g(n)。

在您的情况下，因为O(n^2 *log(n))占主导地位O(n^(3/2) log(n))，它也是一个有效的上限，即使它不那么严格。此外，您可以说您的算法是O(n^3). 问题是，这些大 O 符号中的哪一个为我们提供了有关算法的更多信息？显而易见的答案是较低的答案，这就是我们通常指出这一点的原因。

让事情变得更清楚：假设您可以将球抛向空中 10 米。然后，你可以说你不能扔超过 10m，或者你可以说你不能扔超过 15 米。第一个是更严格的上限这一事实不会使第二个成为错误的陈述。

Answer 2

应用于总和的“大 O 表示法”总是只留下主要（最大的）项。在一个自变量的情况下，只有一个术语会存在。在你的情况下

  O(n^2*log(n) + n^(3/2)*log(n)) = O(n^2*log(n))

因为第一项大于第二项：

  lim(term1/term2) = lim(n^2*log(n) / (n^(3/2)*log(n))) = lim(n^(1/2)) = inf

但看来，您在计算中犯了算术错误：

  (n^2+2n)/n = n + 2, not n^2 + 2 * n

在这种情况下

  O(n*log(n) + 2*log(n) + n^(3/2)*log(n))

最后一项是“n^(3/2)*log(n)”是最大的一项

  O(n*log(n) + 2*log(n) + n^(3/2)*log(n)) = O(n^(3/2)*log(n))