计算机 算法设计题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))2Show that lgn!= θ(n lg n)(Not:that lgn!= θ(n lg n) means t
来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/22 19:39:59
计算机 算法设计题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))2Show that lgn!= θ(n lg n)(Not:that lgn!= θ(n lg n) means t
计算机 算法设计题
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
计算机 算法设计题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))2Show that lgn!= θ(n lg n)(Not:that lgn!= θ(n lg n) means t
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))