算法分析习题课--第4章方案

算法分析习题课第4章作业•第四章：2、3、5、6、10、11、23P994.2在下列情况下求解4.1节的递归关系式T(n)=()2(/2)()gnnTnfn足够小＋否则当①g(n)=O(1)和f(n)=O(n)；②g(n)=O(1)和f(n)=O(1)。解题思路•猜想T(n)是多少？–从特殊情况入手，使用试探或蛮力法解开方程–题目给出的是O()表示的界，结论也应该是类似的界•证明猜想蛮力法设n=2k则:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2T(2k-2)+f(2k-1))+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=…………=2kT(1)+2k-1f(2)+2k-2f(22)+…+20f(2k)=2kg(n)+2k-1f(2)+2k-2f(22)+…+20f(2k)g(n)=O(1)和f(n)=O(n)当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn+c，则：T(n)=T(2k)=2ka+2k-1*2b+2k-2*22b+…+20*2kb+c*(2k-1+2k-2+…+20)=2ka+kb2k+(2k-1)c=(a+c)n–c+bnlog2n=O(nlog2n)证明T(n)=O(nlogn)•n足够小时，T(n)=g(n)=O(1)=O(nlogn)显然成立•假设nk时命题成立，则当n=k时–由归纳假设，T(n/2)=O((n/2)*log(n/2))，即存在正整数c1、n1，当n/2=n1时，T(n/2)=c1*(n/2)*log(n/2)(c1*nlogn)/2–由f(n)=O(n)，存在正整数c2、n2，当n=n2f(n)=c2*n–T(n)=2T(n/2)+f(n)=c1*nlogn+c2*n=(c1+c2)*nlogn=c*nlogn猜想也可以运用技巧•T(1)=1•T(n)=2*T(n/2)+n•T(n)/n=T(n/2)/(n/2)+1•n=2KT(n)/n=k•T(n)=nlogng(n)=O(1)和f(n)=O(1)当g(n)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)=T(2k)=c2k+2k-1d+2k-2d+…+20d=c2k+d(2k-1)=(c+d)n-d=O(n)证明T(n)=O(n)•n足够小时，T(n)=g(n)=O(1)=O(n)显然成立•假设nk时命题成立，则当n=k时–由归纳假设，T(n/2)=O((n/2))，即存在正整数c1、n1，当n/2=n1时，T(n/2)=c1*(n/2)–由f(n)=O(1)，存在正整数c2、n2，当n=n2f(n)=c2–T(n)=2T(n/2)+f(n)=c1*n+c2=O(n)P99-3•根据4.2节开始所给出的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCH(A,low,high,x,j)integermid;if(lowhigh)thenj←0;return;endifmid←(low+high)/2ifx=A(mid)thenj←mid;endif//教材case更简洁直观ifxA(mid)thenBINSRCH(A,low,mid-1,x,j);endififxA(mid)thenBINSRCH(A,mid+1,high,x,j);endifendBINSRCHP99-5•作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。ProcedureTriSearch(A,x,n,j)integerlow,high,p1,p2;low←1;high←n;whilelow≤highdop1←(high+2low)/3p2←(2high+low)/3//roundcase:x=A(p1):j←p1;return:x=A(p2):j←p2;return:xA(p1):high←p1-1:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endThrSearch实例运行1p1←(high+2low)/3p2←(2high+low)/3//round1，231，2•三元查找树的高度?–数学归纳法–递推关系式实例运行{1,2,3,4,5,6,7,8,9}3，694，51，27，8H(n)=H(n/3)+1H(2)=1H(1)=1时间复杂性•以比较为基本运算，•查找成功，内结点，次数=路径长度+1，•查找失败，外结点，次数=路径长度最好平均平均成功O(1)?O(log3(n))O(log3(n))失败O(log3(n))O(log3(n))O(log3(n))•观察：只与外部结点相邻的内结点–有3个外部结点–有2个外部结点，增加1个虚拟的外部结点，结果是I(n)不变，E(n)增加三元比较树的E(n)和I(n)d•E′(n–1)=E′(n)–3d–3+d=E′(n)–2d–3•I(n–1)=I(n)–d⇒2I(n–1)=2I(n)–2d•E′(n–1)–2I(n–1)+3=E′(n)–2I(n)•E′(1)–2I(1)=3•E′(n)–2I(n)=3n•路径总长度的关系：I(n)=[E′(n)–3n]/2三分是否比二分更好？361425798H(n)H(n/3)H(n)=H(n/3)+2H(2)=2H(1)=1树高度接近2log3nP994.6对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设n≤=k(k0)时，E=I+2n成立；则当n=k+1时，确定某个内结点x，而且它的两个儿子都为叶结点（根据二元扩展树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。X此时新树内部结点为k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：Ek+1=Ek-h+2(h+1)（2）Ik+1=Ik+h（3）综合（1）（2）（3）式：Ek+1=Ik+2k+h+2=Ik+1-h+2k+h+2=Ik+1+2(k+1)故命题成立。P99-10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？•最好情况：–对有序文件进行排序•分析–归并的次数不会发生变化----log(n)次–归并中比较的次数会发生变化（两个长n/2序列归并）•最坏情况–两个序列交错大小–需要比较n-1次•最好情况–一个序列完全大于/小于另一个序列–比较n/2次–差异都是线性的，不改变复杂性的阶•最好情况也是nlog(n),平均复杂度nlog(n)。P99-11•写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。procedureMPass(R,n,len,X)integern,len,i;i←1;whilei≤n–2*len+1doMerge(R,i,i+len-1,i+2*len-1,X);i←i+2*len;repeatifi+len–1nthenMerge(R,i,i+len-1,n,X）elseforj=itondoX(j)←R(j)endifendMPassprocedureMSort(R,n)//直接两路合并排序算法，X是辅助文件，其记录结构与R相同integerlen,n;len←1;whilelenndoMPass(R,n,len,X);len←2*len;MPass(X,n,len,R);len←2*len;repeatendMSortP99-23•通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。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+A12B21P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)C12=R+T=A11B12-A11B22+A11B22+A12B22=A11B12+A12B22C21=Q+S=A21B11+A22B11+A22B21-A22B11=A21B11+A22B21C22=P+R-Q+U=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11+(A21-A11)(B11+B12)=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B11-A11B12=A22B22+A21B12P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。