big-o - 大哦分类

Question

假设我有一个具有以下增长的函数：

2000n^2 + log n

我是否有可能得出结论，该函数是属于 类别的函数集的一部分O(n)？

Answer 1

O(some function) 是函数的限制行为。

是否存在一些 C 使得 C*n 描述了您为所有 n 描述的函数的上限？

如果您仔细查看您的函数，您可以将 C 设置为 2000，这样 2000*n^2 = C*n^2...大于 C*n。

所以不，它不是 O(n)。

Answer 2

否，因为对于任何固定 x，O(log n) < O(n^x)，O(2000n^2 + log(n)) = O(n^2)

一个更简单的方法是因为 O(log n) < O(n^x), O(log n) < O(n^2) 所以 O(2000n^2 + log(n)) <= O (2000n^2 + n^2) = O(2001n^2) = O(n^2) 并且由于 O(2000n^2 + log(n)) 有一个 n^2 项，它至少与n^2 给我们 O(2000n^2 + log(n)) >= O(n^2)。现在我们有 O(2000n^2 + log(n)) <= O(n^2) 和 O(2000n^2 + log(n)) >= O(n^2) 所以我们可以得出结论 O( 2000n^2 + log(n)) = O(n^2)