首页计算机计算机基础计算机算法设计与分析 10 第四章作业.pptx

10 第四章作业.pptx

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

本课件讲解第四章分治法的课后习题,包括分治递归式在不同代价函数下的求解、递归形式的二分检索过程、三分检索算法的设计与复杂度分析、由底向上的归并分类算法以取消栈空间,以及手算验证斯特拉森矩阵乘法的子块结果。

第四章习题封面,标示本次习题选取分治法一章的2、3、5、7、11、12、23题
习题P99-2题目页,要求分析分治递归式在不同g(n)与f(n)取值下的时间复杂度
P99-2解答页,展开递归式后说明解为n与n对数之和的量级
查看本课件的文字版(共 19 页,供检索与复制)

第1页:第四章习题封面

第四章习题2,3,5,7,11,12,23

第2页:习题P99-2题目

P99-2

第3页:P99-2:g为O(1)、f为O(n)

P99-2

  • 当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a,f(n)=bn,a、b为常数,令n=2k,则:T(n)=2T(n/2)+bn=4T(n/4)+2bn=…=2kT(n/2k)+kbn=an+bnlog2n=O(nlog2n)

第4页:P99-2:f与g均为O(1)

P99-2当g(n)=O(1)和f(n)=O(1)时,不妨设g(n)=c,f(n)=d,令n=2k,则:T(n)=2T(n/2)+d=4T(n/4)+2d=…=2kT(n/2k)+kd=cn+dlog2n=O(n)

第5页:习题P99-3题目

P99-3

  • 根据4.2节开始所给出的二分检索策略,写一个二分检索的递归过程。

第6页:BINSRCH2过程

Procedure BINSRCH2(A, low, high, x, j) integer mid;iflow≤high thenmid←⌊(low+high)/2⌋ case:x=A(mid):j←mid; return:x>A(mid):BINSRCH2(A, mid+1, high, x, j):x<A(mid):BINSRCH2(A, low, mid-1, x, j) end case elsej←0; endif end BINSRCH2初次调用为BINSRCH2(A,1,n,x,j)

第7页:习题P99-5题目

P99-5

  • 作一个“三分”检索算法,它首先检查n/3处的元素是否等于某个x的值,然后检查2n/3处的元素。这样,或者找到x,或者把集合缩小到原来的1/3。分析算法在各种情况下的计算复杂度。

第8页:ThriSearch过程

Procedure ThriSearch(A, n, x, j) integer low, high, p1, p2low←1; high←n while low≤high dop1←⌊(high+2low)/3⌋p2←⌊(2high+low)/3⌋ case:x=A(p1): j←p1; return:x=A(p2): j←p2; return:x<A(p1): high←p1−1:x>A(p2): low←p2+1: else: low←p1+1; high←p2−1 end case repeatj←0 end ThriSearch

第9页:三分检索的判定树示意

361123456789123456789123456789123456789123456789123456789425798

第10页:三分检索递归式

361425798H(n)H(n/3)H(n)=H(n/3)+2H(3)=3H(2)=2H(1)=1g(n) n足够小H(n)=H(n/3)+f(n)否则g(n)=O(1)f(n)=O(1)

第11页:三分检索的时间复杂度

时间复杂度

  • 成功:
  • O(1),O(log3(n)),O(log3(n))
  • 最好,平均,最坏
  • 失败:
  • O(log3(n)),O(log3(n)),O(log3(n))
  • 最好,平均,最坏

第12页:BINSRCH1过程

procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n;low←1; high←n+1/×high总比可能的取值大1×/ while low<high−1domid←⌊(low+high)/2⌋ if x<A(mid) thenhigh←mid elselow←mid/×x≥A(mid)×/ endif repeat if x=A(low) thenj←low /×检索成功×/ else j←0/×检索失败×/ endif end BINSRCHP99-7 证明BINSRCH1的最好、平均和最坏情况的计算时间对于成功和不成功的检索都是Θ(logn).

第13页:习题P99-7解题思路

P99-7

  • 解题思路:给出BINSRCH1的二元比较树,计算时间与该树的高度有关。设有n个数对应的二元比较树的高度为h(n),显然h(n)=h(n/2)+1=Θ(log(n)).通过分析比较树可知若2k≤n<2k+1时(设树根层数为0,则该树高度为可+1,且包括2n-1个内结点),成功检索出现在第k层或第k+1层,不成功检索的情况出现在第k+1或第k+2层。这两种情况的时间复杂度与该树的高度的数量级一致,都是Θ(log(n))。进而命题得证。
  • n=9(k=3)的比较树如下图所示

第14页:习题P99-7附图

P99-7

第15页:习题P99-11题目

P99-11

  • 写一个“由底向上”的归并分类算法,从而取消对栈空间的利用。实例:1,2,3,4,5,6,7,8,9,101,1,23,3,45,5,67,7,89,9,101,2,45,6,81,4,81,8,10

第16页:MERGESORT1过程

P99-11Procedure MERGESORT1(n) integer low, mid, high, step, kstep ←1; k←⌊logn⌋ while step ≤2kdolow← 1 while low +step−1<n domid ← low + step−1;high ←min{ mid+step, n};MERGE(low,mid,high);low ← high +1; repeatstep ← step×2; repeat end MERGESORT1

第17页:习题P99-23题目

P99-23

  • 通过手算证明(4.9)和(4.10)式确实能得到C11,C12,C21和C22的正确值。

第18页:C11的展开验证

C11=P+S-T+V=(A11+A22)(B11+B22) +A22(B21-B11)-(A11+A12)B22+(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21-A22B11-A11B22-A12B22+A12B21+ A12B22-A22B21-A22B22=A11B11+A12B21T=(A11+A12)B22P=(A11+A22)(B11+B22)U=(A21-A11)(B11+B12)Q=(A21+A22)B11V=(A12-A22)(B21+B22)R=A11(B12+B22)S=A22(B21-B11)

第19页:七个中间量的定义

T=(A11+A12)B22P=(A11+A22)(B11+B22)U=(A21-A11)(B11+B12)Q=(A21+A22)B11V=(A12-A22)(B21+B22)R=A11(B12-B22)S=A22(B21-B11)C12=R+T= A11B12-A11B22+A11B22+A12B22= A11B12+A12B22C21=Q+S= A21B11+A22B11+A22B21-A22B11= A21B11+A22B21

顶部目录