Question

算法复杂度计算中 Max{f,g} = O （f + g ）是否正确?

Answer 1

这里前提需要假设 f ≥ 0 , g ≥ 0

那么 max{f,g} ≤ f + g

所以存在 N = 1 , C = 1.

满足对任意的 x ≥ N , 有 max{f,g} ≤ 1*(f + g)

即: max{f,g} = O(f + g)

证毕#

这里注意反例, 如果没有min{f,g} ≥ 0的条件:

令 f(x) = -x ; g(x) = x;

有 max{f,g} = |-x| - x ;

f + g = 0

那么不存在 实数 C ,也不存在正整数N ,

满足对任意的 x ≥ N ,有 max{f,g} ≤ C*0 = 0