第1页:第二章第三章作业封面
第二章,第三章作业
第2页:作业一题目
作业11.证明:n2=O(n3);
2.证明: 2n2+11n-10=O(n2);
3.证明:O的以下两个性质O(f(n))×O(g(n)) = O(f(n)×g(n));
O(cf(n)) = O(f(n)),其中c是一个正的常数;
4.证明:n3≠O(n2)
第3页:作业一续题
作业15.如果g(n) =(f(n)),则(f(n))+(g(n)) =(f(n));
?6. (cf(n)) =(f(n)),其中c是一个正的常数;
?7. f(n) = (f(n))?8. (f(n))+(g(n)) =(min(f(n),g(n))?9. (f(n))+(g(n)) =(max(f(n),g(n))?10.(f(n))+(g(n)) =(f(n)+g(n))?若成立,证明之;
不成立,举反例。
第4页:证明n²=O(n³)
1证明:n2=O(n3)
- 如果存在两个正常数c和n0,对于所有的n≥n0,有|f(n)|≤c|g(n)|,则记做f(n)=O(g(n))
- 证明
- 对于f(n)=n2,g(n)=n3,当c0=1,n0=1时,当n≥n0时,f(n)≤g(n)。
- 命题得证。
第5页:证明2n²+11n-10=O(n²)
2证明:2n2+11n-10=O(n2)
- 证明
- 对于f(n)=2n2+11n-10, g(n)=n2,当c0=3,n0=10时,有n≥n0时,f(n)≤c0×g(n)
- 命题得证。
第6页:O(f(n))O(g(n))的乘法规则
- 3.1O的性质3:O(f(n))O(g(n)) =O(f(n)g(n))
- 证明:设f1(n)=O(f(n)),则存在正整数n1和c1,使得当n≥n1时,有f1(n)≤c1×f(n)),设f2(n)=O(g(n)),则存在正整数n2和c2,使得当n≥n2时,有f2(n)≤c2×f(n)),当n≥max{n1, n2}时,O(f(n))O(g(n)) =f1(n) f2(n)≤ c1f(n)×c2g(n)=c1c2f(n)g(n),令c0=c1c2,n0= max{n1, n2},命题得证。
第7页:证明O(cf(n))=O(f(n))
- 3.2O(cf(n)) =O(f(n)),其中c是一个正的常数;
- 证明:设f1(n)=O(cf(n)),则存在常数n1,c1,使得n≥n1时,有f1(n)≤c1×cf(n))令c0=c1c,n0=n1,当n≥n0=n1时,有O(cf(n)) =f1(n)≤c1×cf(n)) =c0f(n)=O(f(n))命题得证。
第8页:证明n³≠O(n²)
4n3≠O(n2)
- 反证法
- 假设n3=O(n2),则存在正的常数c0,n0,使得n≥n0时,有n3≤c0n2。
- 令n1=c0+n0,有n1>n0,n1>c0,根据假设有n13≤c0n12,即n1<c0,与假设相矛盾。
- 假设不成立,命题得证。
第9页:Ω(f(n))+Ω(g(n))的证明
- 5.如果g(n) =Ω(f(n)),则Ω(f(n))+Ω(g(n)) =Ω(f(n));?
- 证明设f1(n)=Ω(f(n)),则存在常数n1,c1,使得n≥n1时,有f1(n)≥c1f(n)设f2(n)=Ω(g(n)),则存在常数n2,c2,使得n≥n2时,有f2(n)≥c2g(n);由g(n)=Ω(f(n)),可知存在正常数n3,c3;使得n≥n3时,有g(n)≥c3f(n);当n≥max{n1, n2, n3}时,Ω(f(n))+Ω(g(n)) =f1(n) + f2(n)≥c1f(n) +c2g(n)≥c1f(n) +c2c3f(n) = (c1+c2c3)f(n),令c0=(c1+c2c3),n0= max{n1, n2, n3},命题得证。
第10页:证明Ω(cf(n))=Ω(f(n))
- 证明设f1(n)=Ω(cf(n)),可知,存在正常数n1,c1,使得n≥n1时,有Ω(cf(n))=f1(n)≥c1cf(n)令c0=c1c,n0=n1,命题得证。6Ω(cf(n)) =Ω(f(n)),其中c是一个正的常数;?
第11页:f(n)=Ω(f(n))的判断
f(n) =Ω(f(n)) ?
- 证明令c0= 1, n0= 1,当n≥n0时,f(n)≥c0f(n)恒成立,命题得证。
第12页:Θ(min)规则不成立
- Θ(f(n))+Θ(g(n)) =Θ(min(f(n),g(n))?
- 证明不成立:举反例f(n)= n=Θ(n),g(n)= 1=Θ(1),f3(n)=min{f(n),g(n) } = 1。而f(n)+g(n)= n+1 ≤ cf3(n)=c不成立。命题得证。
第13页:Θ取max的证明
- Θ(f(n))+Θ(g(n)) =Θ(max(f(n),g(n))?
- 证明设f1(n)=Θ(f(n)),则存在正常数n1,c1,c’1,使得n≥n1时有c1f(n)≤f1(n)≤c’1f(n)设f2(n)=Θ(g(n)),则存在正常数n2,c2,c’2,使得n≥n2时有c2g(n)≤f2(n)≤c’2g(n)设f3(n)= max((f(n),g(n)) ;当n≥max{n1, n2}时,令c0=min{c1,c2},c’0=max{c’1,c’2}c0f3(n)≤c0f(n) +c0g(n)≤c1f(n) +c2g(n)≤f1(n) +f2(n)≤c’1f(n) +c’2g(n)≤c’0f(n) +c’0g(n)≤2c’0f3(n)命题得证。Θ(f(n))+Θ(g(n))
第14页:Θ(f(n)+g(n))的证明
- Θ(f(n))+Θ(g(n)) =Θ(f(n)+g(n)) ?
- 证明设f1(n)=Θ(f(n)),则存在正常数n1,c1,c’1,使得n≥n1时有c1f(n)≤f1(n)≤c’1f(n)设f2(n)=Θ(g(n)),则存在正常数n2,c2,c’2,使得n≥n2时有c2g(n)≤f2(n)≤c’2g(n)设f3(n)=f(n)+g(n);当n≥max{n1, n2}时,令c0=min{c1,c2},c’0=max{c’1,c’2}c0f3(n)=c0f(n) +c0g(n)≤c1f(n) +c2g(n)≤f1(n) +f2(n)≤c’1f(n) +c’2g(n)≤c’0f(n) +c’0g(n) =c’0f3(n)命题得证。Θ(f(n))+Θ(g(n))
第15页:作业二题目
作业21.用数学归纳法证明:当n≥1时,2.用数学归纳法证明:3.书中p70,3.2 (1)
第16页:数学归纳法证明求和式
- n=1时,左式=1/2,右式= 1−1/2,命题成立。
- 设n=k时,等式成立,即Σ1/2i= 1−1/2k。
- n=k+1时,左式=Σ1/2i=Σ1/2i+1/2k+1= 1−1/2k+1/2k+1= 1−1/2k+1综上,命题成立。1≤i≤k1≤i≤k+11≤i≤k
第17页:数学归纳法证明取整对数不等式
- 假设c0=1, n0=1时,命题成立。即有⌊logn⌋≤n
- n=1时,⌊log1⌋=0≤1,命题成立。
- 设n=k时,命题成立,即⌊logk⌋≤k
- n=k+1时,⌊log(k+1)⌋≤⌊log2k⌋≤1 +⌊logk⌋≤1+k综上,命题成立。
第18页:解递归式an=n·an-1
- 3.书上p70,3.2解递归关系式an= nan-1, a0=1
- an= nan-1=n(n−1)an-2=n*(n−1)*…*2*1*a0= n*(n−1)*…*2*1= n!