时间复杂度堆等的习题课

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解：,（1）O(n,2,);,(2) O(2,n,) ;,(3)O(1);,(4)O(logn);,(5)O(n)。,解答：O（）的含义是：,令,f(n,),和,g(n,),是自然数集到非负实数集,的两个函数，如果存在一个自然数,n0,和一个常数,c0,使得,nn0,时,f(n),c,g(n,),则称,f(n,),为,(,g(n,)。,因此，如果,limn,f(n)/g(n,),存在，那么,lim,n,f(n)/g(n,),=,f(n,),=,O(g(n,),。,上述O(1)和O(2)在表示同一个函数的时候，,只是常数项的不同。,O(1)=O(2).,解答：从低到高的排列顺寻应该是：,2, logn，n,2/3, 20n, 4n,2, 3,n, n!,主要采用思路：,在相同时间t内，因为采用的相同复杂度的算法，所以新机器完成问题的时间一定是旧机器完成问题规模的1/64。,解答：,1、设在第二台计算机t秒内为完成的算法的规模是m；,故存在,T(n)=3*2,n,=3*2,m,/64;,得：,m=n+6;,2、按照上述解法可以得出：,nl,2,=64n,2,=nl=8n,3、T(n)=8的含义：该算法完成问题的时间跟算法规模n没有任何关系。所以可以在时间t内解决任何规模的问题。,解答：,对于相同规模的算法，XYZ公司的运算处理器是ABC公司的100倍，所以针对相同的时间复杂度，存在如下公式成立：,（1）m=100n;,(2) m,2,=100n,2,=m=10n,(3) m,3,=100n,3,=m=100,1/3,n,(4) m!=100n!=m1),if (odd(n),n=3*n+1,else,n=n/2;,endwhile,/分别按照奇偶数处理操作，但是n随着变化而变化。,解答：,循环的终止操作是n1，所以只有执行n/2的操作才能使循环趋向终止，而奇数的操作，会使算法无法终止。,观察可以知道，,如果n=2,k,，则算法将趋于终止，,按照此假设，,当n=2,k,则,算法中else的执行次数应该是k=logn,，而不会再找到能小于此数据的算法中else的执行次数。故认为算法的下界应该是,(logn);,n是奇数时无法确定何时终止算法，故上界确定不了。,习题1-8,采用有序表实现一个优先队列的优缺点是什么？,答：,优先队列要能实现插入元素和寻找最大值两个操作。,故采用有序表：优点是寻找最大值很简单，时间复杂性为O(1);,缺点是：插入操作复杂，需要大量数据移动和确定插入位置的搜索。,题1-9：,使用常规队列实现优先级队列，insert操作和deletmax运算需要时间是多少？,解答;,常规队列即普通数组；,insert操作时间是：队尾操作是O(1);,队头操作时间需要n次数据移动：O(n);,deletemax操作：,搜索操作时间复杂度是O(n)。,队尾：O(1);,对头需要移动数据：O(n)。,题1-10：,堆的下列元素在什么位置：,（1）第二大键值。,根节点的子结点。,（2）第三大键值。,根节点的最大的子结点的子结点或根的子结点。,（3）最小键值。,叶子结点上。不能确定具体位置。,习题1-11,写一个算法用于检测给定数组A1.n是不是一个堆，说明该算法的时间复杂性。,算法：,所谓检测是不是符合堆，即比较Ai和A2*i和A2*i+1是不是符合堆的定义。,直到,i=n/2（下界）,结束为止，或是检测到不符合堆定义。,i=1;,while(iA2*i) and (AiA2*i+1),then,i+;,else cout非堆；,exit(0); ,cout是一个堆；,exit（0）；,复杂度分析：明显是一个线性搜索结构,（n）,习题1-12：,哪种堆,运算代价,更大，insert还是delete，证明你的答案。两个的时间复杂度相同均为O(logn)。,证明:假设存在一个堆A1.n，插入操作只在堆末尾进行，故根据insert的算法可知仅仅需要实现sift-up即可；,执行delete(i)操作时，如果i在末尾，则无需任何操作，但是如果i不在末尾，则需要将末尾数据上调至此为止，然后依据数据之间的关心进行sift-down或sift-up，故delete运算代价更大一些。,习题1-13：,从n个元素的最大堆中找到,最小的键值,有可能是多快。,算法思想：,只需要按照堆定义，向小的子结点下移寻找即可。,所以最快的应该是沿着树的一支向下移动寻找，树的高度是k，则应该是O(k=logn)。,习题4-15.,有一个整数堆A1.n,通过不断从A中读取数据，然后向B1.n数组插入的方法实现构建堆B，请证明最坏的情况下复杂度是O(nlogn)。,证明：每向B中插入一次数据，则需要调用一次sift_up操作，而执行数据调整的操作应该是当时树的高度，即第i次操作时，执行的数据移动次数应该是logi，故全部操作的数据移动次数应该是log1+log2+.logn=nlogn，故算法时间复杂度应该是O(nlogn),习题4-18,实现二分搜索堆。,算法1.,i=1;,while (iai)&(,2*i+1a2*i+1) i=2*i;,else i=2*i+1;,else /,搜左孩子, if(a2*ia2*i+1)&(,2*i+1=n,),i=2*i;,else i=2*i+1;,return i;,习题4-19,合并两个相同大小的堆A1.n和B1.n。,算法1.,union-heap(A,B),int C2*n;,copy(A,C);,for (i=1;i=1;i-) sift_down(C,i);,明显这个复杂度是O(2n)=O(n),习题4-20.,计算heapsort算法时，寻找最小和最大的元素的比较次数。,分析：,（,a,）,makeheap,(),(b),互换,A1,和,An,；,(c),sift_down操作；,（1）最大元素,执行完makeheap()操作中后，,A1,就是最大元素，所以最坏就是树的高度logn.,（2）最小元素。,最小元素则难以确定处于哪个位置，所以必须令全部数组排序输出完毕之后，才能确定最后一个输出的就是最小元素。,而在这个过程中：,（,a,）,makeheap,(),的复杂度是,logn,；,(,b)for,循环每执行一次，则需要进行一次调换,A1,和,Ai,，,最坏情况下最小元素会被移动到A1中,，而其应该被移动到当前堆的最后一个，,故移动次数应该分别是:log(n-1),log(n-2),.log1。,故完全找出最小元素的最坏情况下总的比较次数应该是：,log1+log2+.,.+log(n-1)+logn.,4.21分治法的求解,设定2个大整数u,v，分别有m位和n位数字，且,n,=,m,，使用通常求法是O(mn)，可以将u和v均看做是n位数字的大整数，用教材中介绍的分治法，算法复杂度是O(n,log3,)。,当m比n大很多时，试设计算法使得能够在O(n,m,log(3/2),)时间内求出uv的值。,解：,1、当n比m小很多时，我们将v分为,n/m段，每段m位。,则计算uv需要n/m次m位乘法运算。,2、每一个m位的运算应用教材中的乘法运算，时间复杂度是O(logm,3,)。,3、综上所述：算法的时间复杂度是：,O(n/m)m,log3,)=O(nm,log(3/2),).,解答：向右循环移位算法。,（1）首先用二分搜索算法在数组ak,n-1中搜索a0的插入位置。即找到位置,p,使得a,pa0=ap+1,。,（2）将,数组段a,0:p,向右循环移位,p-k+1,个位置，使得ak-1移动到a,p,的位置。这时，原数组元素a0及其左边的元素均排列有序。,（3）重复以上处理过程，一直到剩余最后一个数组段为止。,算法分析：,算法中的a0:k-1中元素的移动次数是k,而数组ak,n中的元素的移动次数最多只有1次。因此，算法的总的元素移动次数不超过k,2,+(n-k)。,算法的元素的比较次数不超过：klog(n-k)次。,当kn,1/2,时，算法的时间复杂度是O(n)。,因为移动数据时只需要O(1)的辅助空间。,3,、考虑创建一个大顶堆的过程反复调用,inert(),过程来实现：,Make_heap2,（）,HeapsizeA,=1; /,设定堆的长度,For i=2 to,lengthA,/,数组长度,Do inert();/,不断插入数据，创建堆,问题：,(1),、当输入数组相同时，该程序和,Make_heap,的构建堆是否一致，若是，请给出证明，如果不是，给出一个反例。,(2),、证明：在最坏的情况下，该算法的时间复杂度是,