《算法分析大题》由会员分享，可在线阅读，更多相关《算法分析大题（9页珍藏版）》请在金锄头文库上搜索。
1、1. 写出插入排序、合并排序伪代码，对插入排序进行最坏、最好和平均情况下复杂度分析，写出合并排序的递归方程，并用递归树方法和主方法对递归方程求解。Write the running time of the Merge sort with recurrences. Solve the recurrences with recursion-tree method. 写的运行时间归并排序有复发。解决复发与递归树的方法。算法描述3分The best-case running time is T(n) = c1n + c2(n - 1) + c4(n - 1) + c5(n - 1) + c8(n -
2、1)= (c1 + c2 + c4 + c5 + c8)n - (c2+ c4 + c5 + c8). This running time can be expressed as an + b for constants a and b that depend on the statement costs ci ; it is thus a linear function of n.This worst-case running time can be expressed as an2 + bn + c for constants a, b, and c that again depend o
3、n the statement costs ci ; it is thus a quadratic function of n.分析2分算法描述2分(1) if n = 1T(n) = 2T(n/2) + (n) if n 1.递归方程和求解3分InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key(1) if n = 1T(n) = 2T(n/2) + (n) if n 1. 2.二分查找算法以及复杂性分析 3. Do Exercise
4、 4.1-6 on page 67 in CLRS.4. 公式法求T(n)=4T(n/2)+n T(n)=4T(n/2)+n2 T(n)=4T(n/2)+n3 P75T(n) = 4T(n/2) + n a = 4, b = 2 nlogba = n2; f (n) = n. CASE 1: f (n) = O(n2 ) for = 1. T(n) = (n2).T(n) = 4T(n/2) + n2 a = 4, b = 2 nlogba = n2; f (n) = n2. CASE 2: f (n) = (n2lg0n), that is, k = 0. T(n) = (n2lg n).T
5、(n) = 4T(n/2) + n3 a = 4, b = 2 nlogba = n2; f (n) = n3. CASE 3: f (n) = (n2 + ) for = 1 and 4(n/2)3 cn3 (reg. cond.) for c = 1/2. T(n) = (n3).10 5. Write the running time of the Heapify procedure with recurrences. Solve the recurrences with Master method. Heapify(A, i) l = Left(i); r = Right(i);if
6、(l Ai) largest = l;elselargest = i;if (r Alargest)largest = r;if (largest != i) Swap(A, i, largest);Heapify(A, largest); Fixing up relationships between i, l, and r takes Q(1) time If the heap at i has n elements, how many elements can the subtrees at l or r have? Answer: 2n/3 (worst case: bottom ro
7、w 1/2 full) 答:2 n / 3 So time taken by Heapify() is given by所以时间被Heapify()了T(n) T(2n/3) + Q(1) By case 2 of the master theorem is T(n) =O(lgn)6. proof: with the array representation for storing an n-element heap, the leaves are the nodes indexed by n/2+1，n/2+2,n. (10 points) 证明:与数组表示法来存储一个n元素堆,树上的叶子
8、节点索引(n/2(+ 1,(n/2(+ 2,n。(10分)Because a leaf in a heap is a node that has no left son, so for the first leaf that has no children, 2i n. That is, i = n/2+1，n/2+2,n. 7. Heapsort(A)BuildHeap(A);for (i = length(A) downto 2) Swap(A1, Ai);heap_size(A) -= 1;Heapify(A, 1);We know that the call to BuildHeap(
9、) takes O(n) time. Each of the n - 1 calls to Heapify() takes O(lg n) time. Thus the total time taken by HeapSort() = O(n) + (n - 1) O(lg n)= O(n) + O(n lg n)= O(n lg n) 8. CountingSort(A, B, k)for i=1 to kCi= 0;for j=1 to nCAj += 1;for i=2 to kCi = Ci + Ci-1; For j=n downto 1BCAj = Aj;CAj -= 1;Anal
10、ysze its running time. Selection problemRandomizedSelect(A, p, r, i) if (p = r) then return Ap; q = RandomizedPartition(A, p, r) k = q - p + 1; if (i = k) then return Aq; / not in book if (i k) then return RandomizedSelect(A, p, q-1, i); else return RandomizedSelect(A, q+1, r, i-k);9. Write an algor
11、ithm of the selection problem that the worst-case running time is linear-time. 编写一个算法的选择问题,最坏的运行时间是线性时间。1.Divide n elements into groups of 5划分为一组,5 n个元素2.Find median of each group每组的中位数找到3.Use Select() recursively to find median x of the n/5使用Select()递归地找到x的中位数(n/5(4.Partition the n elements around
12、x. Let k = rank(x) 分区的n个元素在x。让k =等级(x)5.if (i = k) then return xif (i k) use Select() recursively to find (i-k)th smallest element in last partitionT(n)=T(1/5n)+T(7/10n)+ (n)10. Describe the execution of the Kruskals algorithm and Prims algorithm. 描述执行克鲁斯卡算法和呆板的的算法。HBCGEDFA141036452915811. Describe
13、the execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices. Each pass relaxes the edges in the order (t,x)(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y) (15 points) 2描述执行传达员福特算法。源是顶点年代。d值显示在顶点。每一个通过放松边缘的顺序(t,x)(t,y),(t,z),(x,t),(y,x,y,z),(z、x),(z,s),(s,t),(s,y)(15分)12. Compute shortest paths with matrix multiplication and the Floyd-Warshall algorithm for the following graph. 计算最短路径与矩阵乘法和弗洛伊德沃肖尔算法对以下图。13. Proof: Subpaths of shortest paths are shortest paths. (8 points)4证明:子路是最短路径的最短路径。(8分)
