是什么O(n) + O(log(n))降低？我的猜测是O(n)但不能给出严格的推理。
O(n) + O(log(n))
O(n)
我知道O(n) + O(1)应该减少到，O(n)因为O(1)这只是一个常数。
O(n) + O(1)
O(1)
好吧，因为O( f(n) ) + O( g(n) ) = O ( f(n) + g(n) )我们只是试图计算f(n)这样一个f(n) > n + log(n)
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)
log(n) < n
f(n) > 2n > n + log(n)
因此 O(f(n)) = O(2n) = O(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)将“主导”我们的算法并决定其时间复杂度。
O( f(n) ) + O( g(n) ) = O( f(n) )
c*f(n)>g(n)
