算法课件全121301ADA06分治法合并排序

1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,Review of last class,The string match algorithm and its best-case, worst-case and average-case analysis,In last lecture, we have learned:,Brute force method and its advantages and disadvantages,The bubble sort algorithm and its best-case, worst-case and average-case analysis,Divide And Conquer (I),Chapter 4,2、Application to combinatorial problem Chess board cover,3、Application to numerical problem Strassens matrix multiplication,*4、A

2、pplication to geometric problem Closest pair,1、Application to sorting problem Merge sort, Quick sort,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should be able to Understand the divide-and-conquer technique Master the idea of merge sort algorithm Master the best-case, worst-case and average-case analysis of merge sort algorithm,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Example,The brute force algorithm f

3、or above problem:,1. void max_min(int A,int 8. 9. ,How to find both the maximum and minimum elements in an array of size n? 8, 3, 6, 2, 1, 9, 4, 5, 7,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Examples (cont.),Can we solve this problem much better?,Time complexity analysis of above algorithm,T(n) = 2n-2,The answer is yes, we can solve it like the following,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Improvement algorithm,1. void maxmin(int A,int 12. 13. ,20

4、19/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Improvement algorithm (cont.),14. else 15. mid = (low + high) / 2; 16. maxmin(A, 20. 21. ,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Examples (cont.),Time complexity analysis of improvement algorithm The basic operation is comparison, so let T(n) denotes the comparisons. For simplicity, we assume n is a power of 2. When n=2, the algorithm do one comparison (by row 5); When n2, the algorithm do two recursive calls of

5、 n/2 elements (by row 16 and 17) and do two comparisons (by row 18 and 19). So we can get the recurrence relation as follow:,2019/6/21,10,2012-2013-01 Design and Analysis of Algorithm SCUN,Examples (cont.),Time complexity of original algorithm,Time complexity of improvement algorithm,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,Divide-and-Conquer Technique,A powerful design technique that is used to solve a variety of problems, is probably the best-known general algorithm desi

6、gn technique. Its basic idea is that it divides the original problem into several subproblems and then get the solution of the original problem based on solving each subproblem one by one. General framework Divide the problem into a number of subproblems of smaller size (generally 2 subproblems) Conquer (solve) the subproblems. If the size is smaller than a threshhold, solve straightforward Otherwise, recursively invoke the algorithm Combine the solutions to obtain a solution for the original pr

7、oblem.,2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Divide-and-Conquer Technique (cont.),subproblem 2 of size n/2,subproblem 1 of size n/2,a solution to subproblem 1,a solution to the original problem,a solution to subproblem 2,a problem of size n,2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Divide-and-Conquer Technique (cont.),Procedure DAC ( P ) if | P | n0 then return (G(P) else divide P into smaller subinstances P1, P2, , Pa for(i=1, i=a; i+) Si = DAC(Pi

8、) end for return (Combine(S1, , Sa) end if,Threshhold to indicate the size of input is small enough,A procedure to solve P directly,A procedure to combine the solutions for subproblems,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,General Divide-and-Conquer Recurrence,T(n) = aT(n/b) + f (n) where f(n) (nd), d 0,Master Theorem: If a bd, T(n) (nlog b a ),Note: The same results hold with O instead of .,Examples: T(n) = 4T(n/2) + n T(n) ?,T(n) = 4T(n/2) + n2 T(n) ?,T(n) = 4T(n/2) +

9、 n3 T(n) ?,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Merge Sort,Merge sort is a member of sorting problem, is an example algorithm that reveals the essence of divide-and conquer technique Its idea is Directly derived from divide and conquer Divide: divide the list r1, r2, , rn into two equal length sublists r1, r2, , rn/2 and rn/2+1, r2, , rn Conquer: recursively merge sort the two sublists respectively, and get two ordered sublists. Combine: merge the two sorted sublists into one ordered list,2019/6/21,17,2012-2013-01 Design and Analysis of Algorithm SCUN,The Merge Sort Algorithm,ALGORITHM MergeSort(A, first, last) /Input: A: An array of orderable elements first: the index of the first element in A last: the index of the last element in A /Output: Array A sorted in n

《算法课件全121301ADA06分治法合并排序》由会员E****分享，可在线阅读，更多相关《算法课件全121301ADA06分治法合并排序》请在金锄头文库上搜索。