算法分析大题

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 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 on the statement costs ci it is thus a quadratic function of n 分析2分 算法描述算法描述 2 分分 1 if n 1 T n 2T n 2 n if n 1 递归方程和求解递归方程和求解 3 分分 InsertionSort A n for i 2 to n key A i j i 1 while j 0 and A j key A j 1 A j j j 1 A j 1 key 1 if n 1 T n 2T n 2 n if n 1 2 二分查找算法以及复杂性分析 3 Do Exercise 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 P75 T 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 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 l A i largest l else largest i if r A largest largest r if largest i Swap A i largest Heapify A largest Fixing up relationships between i l and r takes 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 row 1 2 full 答 2 n 3 So time taken by Heapify is given by所以时间被 Heapify 了 T n T 2n 3 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 元素堆 树上的叶 子节点索引 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 le af 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 A 1 A i heap size A 1 Heapify A 1 We know that the call to BuildHeap 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 k C i 0 for j 1 to n C A j 1 for i 2 to k C i C i C i 1 For j n downto 1 B C A j A j C A j 1 Analysze its running time Selection problem RandomizedSelect A p r i if p r then return A p q RandomizedPartition A p r k q p 1 if i k then return A q 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 algorithm 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 x Let k rank x 分区的 n 个元素在 x 让 k 等级 x 5 if i k then return x if i k use Select recursively to find i k th smallest element in last partition T n T 1 5n T 7 10n n 10 Describe the execution of the Kruskal s algorithm and Prim s algorithm 描述执行克 鲁斯卡算法和呆板的的算法 HBC GED F A 14 10 3 64 5 2 9 15 8 11 Describe 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