可能重复:将
O添加到不同的例程时
什么O(n) + O(log(n))减少到？我的猜测是O(n)但不能给出严谨的推理.
我的理解O(n) + O(1)应该减少O(n),因为O(1)仅仅是一个常数.
Dan*_*zer 12
好吧,因为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)将"支配"我们的算法并决定其时间复杂度.