Question

计算机 算法设计题1、试证明下面的定理：(1) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g

Answer 1

1. (1)

存在常数c1, f(n) <= c1 * s(n)

存在常数c2, g(n) <= c2 * r(n)

令常数C = max(c1, c2)

则 f(n) + g(n) <= c1 * s(n) + c2 * r(n) <= C * (s(n) + r(n)) = O(s(n) + r(n))1.(2)

令常数D = c1 * c2

则f(n) * g(n) <= c1 * s(n) * c2 * r(n) = D * s(n) * r(n) = O(s(n)*r(n))