总和大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符号的

回答

相关问题