大哦分類

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）