假设我有一个具有以下增长的函数：
2000n^2 + log n
我是否有可能得出结论，该函数是属于 类别的函数集的一部分O(n)？
问问题
130 次
2 回答
0
O(some function) 是函数的限制行为。
是否存在一些 C 使得 C*n 描述了您为所有 n 描述的函数的上限？
如果您仔细查看您的函数，您可以将 C 设置为 2000，这样 2000*n^2 = C*n^2...大于 C*n。
所以不，它不是 O(n)。
于 2013-05-07T13:18:38.317 回答
0
否，因为对于任何固定 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)
于 2013-05-07T13:13:43.403 回答