Question

计算机 算法设计题

1、试证明下面的定理： (1) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n)) (2) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))
2
Show that lgn! = θ(n lg n)
(Not: that lgn! = θ(n lg n) means that c1nlgn≦lg (n!) ≦ c2nlgn, for some constants c1 c2.and n0 when n >= n0 )
解：limlogn！/lognn
=limlog(根号2πn（nn/en）)/nlongn
=lim1/2log（2π）+1/2logn+nlogn-nloge/nlogn
=lim（1/2log（2π）/nlogn+1/2/n+1-1/lnn
=1
求解给翻译一下

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))