大哦分类

Question

说，我认为有以下增长的函数：

2000n^2 + log n 

是否有可能让我得出这样的结论功能是一套落入O(n)类功能的一部分吗？

Answer 1

O（某些函数）是函数的限制行为。

是否存在一些C以至于C * n描述了您所描述的所有n的函数的上限？

如果你仔细看看你的函数，你可以将C设置为2000，使得2000 * n^2 = C * n^2 ...大于C * n。

所以不，它不是O（n）。

Answer 2

否因为O（log n）的<为O（n^x）的任何固定的x，O（2000N^2 +的log（n））= O（N^2）

更简单的方法以查看这是因为O（log n）= 0（2000n^2），O（log n），O（log n）< O（n^2）等等O（2000n^2 + log（n）由于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）