为什么只有一个关于复杂性 类 的陈述是正确的？

Question

显然下面问题的正确答案是（C），但为什么在我们知道 n 的值之前其他选项都不正确？

如果 n=1，除了 (B) 之外，所有这些似乎都是正确的！我哪里错了？

Which of the following is not O(n²)?

(A) 15¹⁰ * n + 12099
(B) n^1.98
(C) n³ / √n
(D) 2²⁰ * n

Answer 1

None 个选项的顺序为 n^2。

(15^10) * n + 12099 是 n

阶

n^1.98 的阶数为 n^1.98

n^3 / (sqrt(n)) 的阶数为 n^2.5

(2^20) * n 是 n 阶

您可以通过将一个函数除以另一个函数来检查两个函数是否具有相同的顺序。当 n 趋于无穷大时，它应该趋于趋于恒定。

Answer 2

Wikipedia 说：-

Big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

上界意味着f(n) = n可以表示为O(n), O(n²), O(n³ ), 和其他但不是在像 O(1), O(log n) 这样的其他函数中。

所以，朝同一个方向前进，现在您可以轻松地消除选项，如下所示:-

1. 15¹⁰ * n + 12099 < c * n²，对于某些 n > √12100 即 n > 110 --- 因此是 O(n²).

2. n^1.98 < n²，对于所有 n > 1 --- 并且是 O(n²).

3. n³ / √n = n^5/2 > n² 对于所有 n > 1 --- 因此，不是 O(n²)。

4. 2²⁰ * n = 1024*1024*n < c* n² 所有 n > 1 ，其中 c = 1024*1024 --- 因此，是 O(n²).

因此，唯一不满足O(n²)的选项是选项C，即f(n) = (n^3 / (sqrt(n)))。因此，这里 (n³ / (sqrt(n))) 不等于 O(n²).

Answer 3

虽然 Shekhar Suman 的回答解释了为什么官方答案在每种情况下都是正确的，但它并没有回答这部分问题：“显然以下问题的正确答案是 (C)，但是为什么其他选项不正确 直到我们知道 n 的值？ 如果 n = 1，除了 (B)，所有这些似乎都是正确的！ 我哪里错了？”（我的突出显示）。

我建议我用粗体显示的前两部分表明提问者在提问时没有掌握的内容，即 O-notation 用于表达有关函数的信息，而不是有关特定值的信息表达式。

这意味着说“如果 n = 1，f(n) 是 O(n²)”是没有意义的，因为这是关于一个值 f(1) 的陈述，而不是关于函数 f.

类似地，“until we know the value of n”在谈论函数时没有任何意义，因为n是一个绑定变量，即仅用于将n与涉及n的表达式相关联，以便定义函数。