首页计算机计算机基础计算机算法设计与分析 09 第二三章作业.pptx

09 第二三章作业.pptx

页数:18页文件大小:108.7 KB来源: 计算机算法设计与分析ppt课件

本课件为第二章与第三章的习题讲解,围绕渐近记号的证明展开,包括大O与Ω、Θ记号的定义使用、传递与算术运算性质的推导、n³不属于O(n²)的反证,以及用数学归纳法证明求和式与取整对数不等式、求解递归关系式等内容。

第二、三章作业封面,标示本次作业覆盖渐近表示证明、数学归纳法与递归关系式
作业一题目页,列出大O记号与Θ记号若干性质的证明题
作业一续题页,继续列出Θ与Ω记号相关性质的判断与证明要求
查看本课件的文字版(共 18 页,供检索与复制)

第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!
顶部目录