时间复杂度堆等的习题课.ppt

1、解： （1）O(n2); (2) O(2n) ; (3)O(1); (4)O(logn); (5)O(n)。,解答：O（）的含义是： 令f(n)和g(n)是自然数集到非负实数集 的两个函数，如果存在一个自然数n0和一个常数 c0,使得nn0时f(n)cg(n),则称f(n)为(g(n)。 因此，如果limnf(n)/g(n)存在，那么 limnf(n)/g(n) = f(n)=O(g(n)。 上述O(1)和O(2)在表示同一个函数的时候，只是常数项的不同。 O(1)=O(2).,解答：从低到高的排列顺寻应该是： 2, logn，n2/3, 20n, 4n2, 3n, n!,主要采用思路：在相同

2、时间t内，因为采用的相同复杂度的算法，所以新机器完成问题的时间一定是旧机器完成问题规模的1/64。,解答： 1、设在第二台计算机t秒内为完成的算法的规模是m； 故存在T(n)=3*2n=3*2m/64; 得：m=n+6; 2、按照上述解法可以得出： nl2=64n2=nl=8n 3、T(n)=8的含义：该算法完成问题的时间跟算法规模n没有任何关系。所以可以在时间t内解决任何规模的问题。,解答： 对于相同规模的算法，XYZ公司的运算处理器是ABC公司的100倍，所以针对相同的时间复杂度，存在如下公式成立： （1）m=100n; (2) m2=100n2=m=10n (3) m3=100n3=m=

3、1001/3n (4) m!=100n!=mn+log100=n+6.64 (注意：解相同时间复杂度的问题的时间是另外算法的100倍）,习题1-7 试确定下面程序段的下界： while (n1) if (odd(n) n=3*n+1 else n=n/2; endwhile /分别按照奇偶数处理操作，但是n随着变化而变化。,解答： 循环的终止操作是n1，所以只有执行n/2的操作才能使循环趋向终止，而奇数的操作，会使算法无法终止。 观察可以知道，如果n=2k，则算法将趋于终止， 按照此假设，当n=2k则,算法中else的执行次数应该是k=logn，而不会再找到能小于此数据的算法中else的执行次

4、数。故认为算法的下界应该是 (logn); n是奇数时无法确定何时终止算法，故上界确定不了。,习题1-8 采用有序表实现一个优先队列的优缺点是什么？ 答： 优先队列要能实现插入元素和寻找最大值两个操作。 故采用有序表：优点是寻找最大值很简单，时间复杂性为O(1); 缺点是：插入操作复杂，需要大量数据移动和确定插入位置的搜索。,题1-9： 使用常规队列实现优先级队列，insert操作和deletmax运算需要时间是多少？ 解答; 常规队列即普通数组； insert操作时间是：队尾操作是O(1); 队头操作时间需要n次数据移动：O(n); deletemax操作： 搜索操作时间复杂度是O(n)。

5、队尾：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); c

6、out是一个堆； 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个元素的最大堆中找到最小的键值有可能是多快。 算法思想：

7、只需要按照堆定义，向小的子结点下移寻找即可。 所以最快的应该是沿着树的一支向下移动寻找，树的高度是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;

8、while (iai),else /搜左孩子 if(a2*ia2*i+1),习题4-19 合并两个相同大小的堆A1.n和B1.n。 算法1. union-heap(A,B) int C2*n; copy(A,C); for (i=1;i=n;i+) insert(Bi,C); sift_up(C); 算法复杂度明显是O(nlogn);,算法2. 保证线性搜索。 union(A,B) int C2*n; copy(A,C); copy(B,C); for(i=n;i=1;i-) sift_down(C,i); 明显这个复杂度是O(2n)=O(n),习题4-20. 计算heapsort算法时，寻找

9、最小和最大的元素的比较次数。 分析： （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-

10、2),.log1。 故完全找出最小元素的最坏情况下总的比较次数应该是： log1+log2+.+log(n-1)+logn.,4.21分治法的求解 设定2个大整数u,v，分别有m位和n位数字，且n=m，使用通常求法是O(mn)，可以将u和v均看做是n位数字的大整数，用教材中介绍的分治法，算法复杂度是O(nlog3)。 当m比n大很多时，试设计算法使得能够在O(nmlog(3/2)时间内求出uv的值。,解： 1、当n比m小很多时，我们将v分为n/m段，每段m位。 则计算uv需要n/m次m位乘法运算。 2、每一个m位的运算应用教材中的乘法运算，时间复杂度是O(logm3)。 3、综上所述：算法的时

11、间复杂度是： O(n/m)mlog3)=O(nmlog(3/2).,解答：向右循环移位算法。 （1）首先用二分搜索算法在数组ak,n-1中搜索a0的插入位置。即找到位置p使得apa0=ap+1。 （2）将数组段a0:p向右循环移位p-k+1个位置，使得ak-1移动到ap的位置。这时，原数组元素a0及其左边的元素均排列有序。 （3）重复以上处理过程，一直到剩余最后一个数组段为止。,算法分析： 算法中的a0:k-1中元素的移动次数是k,而数组ak,n中的元素的移动次数最多只有1次。因此，算法的总的元素移动次数不超过k2+(n-k)。 算法的元素的比较次数不超过：klog(n-k)次。 当kn1/2时，算法的时间复杂度是O(n)。 因为移动数据时只需要O(1)的辅助空间。,3、考虑创建一个大顶堆的过程反复调用inert(