如何檢查的複雜功能

Question

大O我有這樣的：

a) f(n) = n 
b) f(n) = 1045n 
c) f(n) = n2 + 70 
d) f(n) = 7n + 3 
e) f(n) = Cn + D (where C and D are both constants) 
f) f(n) = 8 
g) f(n) = n3 + n + 1 
h) f(n) = 4n + 2log n + 5 

我要檢查，如果他們的大O符號爲O（n）。

我該如何確定它？

而如何找到大O符號爲以下功能：

a) f(n) = 3n3 + n 
b) f(n) = 3 log n + 5n 
c) f(n) = 3n2 + 5n + 4 
d) f(n) = 3n3 + n2 + 5n + 99 

Answer 1

f(x) is O(g(x)) if there exists a constant c such that f(x) < c*g(x) 

你應該看看「最大」 asymptoticall因素的功能（最高指數或類似的東西）和這將是你的大Ø

例子：f(n) = 2^n + n^5 + n^2 + n*log(n) + n
該功能具有影響大O 5個不同的因素，排序從大到小，所以這一塊將是O（2^N）。丟掉2^n，現在f(n)是O(n^5)。

常量是O（1）。

希望我解釋得很好

Answer 2

一般功能的大O符號是由出現n的最大功率測量。在你的情況下，這將是n²，因爲唯一的另一個因素是恆定的70。

編輯：原帖僅包含函數f（N）=N²+ 70

Answer 3

見this answer。

總之，沒有確定大O結果的方法。嚴格地說，任何最終（對於某些n）總是比你的函數更大的函數，就是它的大部分。在實踐中，你正在尋找儘可能緊湊的界限。如果函數的唯一分量是n中的多項式，那麼大O將是最大功率n，其出現（或更確切地說，該功率爲n）。另一個有用的事情要知道，log n是低於n（但高於常數）。