页数:19页文件大小:150.9 KB来源: 计算机算法设计与分析ppt课件
本课件讲解第四章分治法的课后习题,包括分治递归式在不同代价函数下的求解、递归形式的二分检索过程、三分检索算法的设计与复杂度分析、由底向上的归并分类算法以取消栈空间,以及手算验证斯特拉森矩阵乘法的子块结果。
第四章习题2,3,5,7,11,12,23
P99-2
P99-2
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)
P99-3
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)
P99-5
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
361123456789123456789123456789123456789123456789123456789425798
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)
时间复杂度
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).
P99-7
P99-7
P99-11
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 MERGESORT1P99-23
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)
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
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}