时间复杂度堆等的习题课

解：（1）O(n2);(2)O(2n);(3)O(1);(4)O(logn);(5)O(n)。解答：O（）的含义是：令f(n)和g(n)是自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c0,使得nn0时f(n)cg(n),则称f(n)为(g(n))。因此，如果limnf(n)/g(n)存在，那么limnf(n)/g(n)=》f(n)=O(g(n))。上述O(1)和O(2)在表示同一个函数的时候，只是常数项的不同。O(1)=O(2).解答：从低到高的排列顺寻应该是：2,logn，n2/3,20n,4n2,3n,n!主要采用思路：在相同时间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=1001/3n•(4)m!=100n!=mn+log100=n+6.64(注意：解相同时间复杂度的问题的时间是另外算法的100倍）习题1-7试确定下面程序段的下界：while(n1)if(odd(n))n=3*n+1elsen=n/2;endwhile//分别按照奇偶数处理操作，但是n随着变化而变化。•解答：•循环的终止操作是n1，所以只有执行n/2的操作才能使循环趋向终止，而奇数的操作，会使算法无法终止。观察可以知道，如果n=2k，则算法将趋于终止，按照此假设，当n=2k则,算法中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写一个算法用于检测给定数组A[1..n]是不是一个堆，说明该算法的时间复杂性。算法：所谓检测是不是符合堆，即比较A[i]和A[2*i]和A[2*i+1]是不是符合堆的定义。直到i=n/2（下界）结束为止，或是检测到不符合堆定义。i=1;while(i=n/2){if((A[i]A[2*i])and(A[i]A[2*i+1]))theni++;else{cout非堆；exit(0);}}cout是一个堆；exit（0）；复杂度分析：明显是一个线性搜索结构（n）习题1-12：哪种堆运算代价更大，insert还是delete，证明你的答案。两个的时间复杂度相同均为O(logn)。证明:假设存在一个堆A[1..n]，插入操作只在堆末尾进行，故根据insert的算法可知仅仅需要实现sift-up即可；执行delete(i)操作时，如果i在末尾，则无需任何操作，但是如果i不在末尾，则需要将末尾数据上调至此为止，然后依据数据之间的关心进行sift-down或sift-up，故delete运算代价更大一些。习题1-13：从n个元素的最大堆中找到最小的键值有可能是多快。算法思想：只需要按照堆定义，向小的子结点下移寻找即可。所以最快的应该是沿着树的一支向下移动寻找，树的高度是k，则应该是O(k=logn)。习题4-15.有一个整数堆A[1..n],通过不断从A中读取数据，然后向B[1..n]数组插入的方法实现构建堆B，请证明最坏的情况下复杂度是O(nlogn)。证明：每向B中插入一次数据，则需要调用一次sift_up操作，而执行数据调整的操作应该是当时树的高度，即第i次操作时，执行的数据移动次数应该是logi，故全部操作的数据移动次数应该是log1+log2+...logn=nlogn，故算法时间复杂度应该是O(nlogn)习题4-18实现二分搜索堆。算法1.i=1;while(in){if(x==a[i])returni;else{if((xa[i])&&(2*i+1=n))//搜右孩子if(a[2*i]a[2*i+1])i=2*i;elsei=2*i+1;else//搜左孩子{if((a[2*i]a[2*i+1])&&(2*i+1=n))i=2*i;elsei=2*i+1;}}}returni;习题4-19合并两个相同大小的堆A[1..n]和B[1..n]。算法1.union-heap(A,B){intC[2*n];copy(A,C);for(i=1;i=n;i++){insert(B[i],C);sift_up(C);}}算法复杂度明显是O(nlogn);算法2.保证线性搜索。union(A,B){intC[2*n];copy(A,C);copy(B,C);for(i=n;i=1;i--)sift_down(C,i);}明显这个复杂度是O(2n)=O(n)习题4-20.计算heapsort算法时，寻找最小和最大的元素的比较次数。分析：（a）makeheap()(b)互换A[1]和A[n]；(c)sift_down操作；（1）最大元素执行完makeheap()操作中后，A[1]就是最大元素，所以最坏就是树的高度logn.（2）最小元素。最小元素则难以确定处于哪个位置，所以必须令全部数组排序输出完毕之后，才能确定最后一个输出的就是最小元素。而在这个过程中：（a）makeheap()的复杂度是logn；(b)for循环每执行一次，则需要进行一次调换A[1]和A[i]，最坏情况下最小元素会被移动到A[1]中，而其应该被移动到当前堆的最后一个，故移动次数应该分别是: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(nlog3)。当m比n大很多时，试设计算法使得能够在O(nmlog(3/2))时间内求出uv的值。•解：•1、当n比m小很多时，我们将v分为n/m段，每段m位。•则计算uv需要n/m次m位乘法运算。•2、每一个m位的运算应用教材中的乘法运算，时间复杂度是O(logm3)。•3、综上所述：算法的时间复杂度是：•O((n/m)mlog3)=O(nmlog(3/2)).解答：向右循环移位算法。（1）首先用二分搜索算法在数组a[k,n-1]中搜索a[0]的插入位置。即找到位置p使得a[p]a[0]=a[p+1]。（2）将数组段a[0:p]向右循环移位p-k+1个位置，使得a[k-1]移动到a[p]的位置。这时，原数组元素a[0]及其左边的元素均排列有序。（3）重复以上处理过程，一直到剩余最后一个数组段为止。算法分析：算法中的a[0:k-1]中元素的移动次数是k,而数组a[k,n]中的元素的移动次数最多只有1次。因此，算法的总的元素移动次数不超过k2+(n-k)。算法的元素的比较次数不超过：klog(n-k)次。当kn1/2时，算法的时间复杂度是O(n)。因为移动数据时只需要O(1)的辅助空间。3、考虑创建一个大顶堆的过程反复调用inert()过程来实现：Make_heap2（）{Heapsize[A]=1;//设定堆的长度Fori=2tolength[A]//数组长度Doinert();//不断插入数据，创建堆}问题：(1)、当输入数组相同时，该程序和Make_heap的构建堆是否一致，若是，请给出证明，如果不是，给出一个反例。(2)、证明：在最坏的情况下，该算法的时间复杂度是(log)nn