algorithm - 大 O 符号之和

Question

可能重复：
将不同的例程加在一起时的大 O

O(n) + O(log(n))减少到什么程度？我的猜测是O(n)但不能给出严格的推理。

我理解O(n) + O(1)应该减少到O(n)因为O(1)只是一个常数。

Answer 1

好吧，因为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)将“主导”我们的算法并决定它的时间复杂度。

Answer 2

订单总是减少到更高的订单项。我可以给你直观的推理。假设你有O(n + n^2). 那么哪个部分会在运行时扮演更重要的角色呢？n 或 n^2。显然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.

我想你现在明白了，

Answer 3

答案是 O(n)。O(log n) 小于 O(n)。所以它们的加法求和最大值，即 O(n)。