總和大O符號的

可能重複：
Big O when adding together different routines 總和大O符號的

是什麼O(n) + O(log(n))減少？我的猜測是O(n)，但不能給出一個嚴格的推理。

我知道O(n) + O(1)應該減少到O(n)，因爲O(1)只是一個常數。

來源

2012-10-18 Will Best

你不應該做自己的功課？ – 2012-10-18 03:34:21

@Yuck對不起，我沒有找到該帖子..謝謝 –

因爲O(f(n)) + O(g(n)) = O (f(n) + g(n))嗯，我們只是試圖計算f(n)這樣f(n) > n + log(n)

由於隨着n充分log(n) < n我們可以說，f(n) > 2n > n + log(n)

因此O(f(n)) = O(2n) = O(n)

在更普遍的意義上說，O(f(n)) + O(g(n)) = O(f(n))如果c*f(n)>g(n)爲一些常數c。爲什麼？因爲在這種情況下，f(n)將「支配」我們的算法並決定其時間複雜度。

來源

2012-10-18 03:35:55 jozefg

答案是O（n）。 O（log n）小於O（n）。，因此它們的加法總和爲O（n）的最大值。

來源

2012-10-18 03:35:11 vinu

訂單總是被縮減爲更高的訂單條款。我可以給你直觀的推理。假設你有O(n + n^2)。那麼哪個部分在運行時會扮演更重要的角色呢？ n或n^2。顯然n^2。因爲當n增加或減少時，你將不會注意到n的影響。

作爲例子，

let n = 100, then n^2 = 10000 
means n is 0.99% and n^2 is 99.01% of total running time. 
What would you consider for runtime? 
if n is increased then this difference is clearer.

我想你現在明白了，

來源

2012-10-18 03:40:46 taufique

總和大O符號的

回答

相關問題