大O符号的总和 [英] Sum of big O notation

问题描述

可能重复：
  大O相加不同的程序时，

这是什么 O（N）+ O（日志（N））减少？我的猜测是 O（N），但不能给出严格的推理。

What does O(n) + O(log(n)) reduce to? My guess is O(n) but can not give a rigorous reasoning.

据我了解 O（N）+ O（1）应减少到 O（N），因为 O（1）仅仅是一个常数。

I understand O(n) + O(1) should reduce to O(n) since O(1) is just a constant.

推荐答案

嗯，因为 0（F（N））+ O（G（N））= O（F（N）+ G（ N））我们只是试图计算出 F（N），使得 F（N）＆GT; N +的log（n）

Well since O( f(n) ) + O( g(n) ) = O ( f(n) + g(n) ) We are simply trying to calculate an f(n) such that f(n) > n + log(n)

由于随着n充分的log（n）＆LT; ñ我们可以说， F（N）＆GT; 2N＆GT; N +的log（n）

Since as n grows sufficiently log(n) < n we can say that f(n) > 2n > n + log(n)

因此​​ 0（F（N））= O（2N）= O（N）

在更普遍的意义， 0（F（N））+ O（G（N））= O（F（N））如果 C * F（N）＆GT; G（N）对于一些常数c。为什么？因为在这种情况下， F（N）将主宰我们的算法，并决定它的时间复杂度。

In a more general sense, O( f(n) ) + O( g(n) ) = O( f(n) ) if c*f(n)>g(n) for some constant c. Why? Because in this case f(n) will "dominate" our algorithm and dictate its time complexity.

这篇关于大O符号的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！