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

计算机 算法设计题
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