算法课件全121301ADA09减治法减常因子算法I

Decrease and Conquer (I),Chapter 5,Introduction to Decrease-and-Conquer Decrease-by-a-Constant-Factor Algorithms The Binary Search Fake-coin Problem Russian Peasant Multiplication Josephus Problem,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the basic idea and all kinds of variations of decrease and conquer technique Master the binary search algorithm and its best-case, worst-case and average-case analysis Understand the fake coin problem and its solution Be familiar with the Russian peasant multiplication method Understand the josephus problem and its solution,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Decrease-and-Conquer (basic idea),Reduce problem instance to smaller instance of the same problem Solve smaller instance Extend solution of smaller instance to obtain solution to original instance,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,3 Types of Decrease and Conquer,Decrease by a constant (usually by 1) Insertion sort Graph traversal algorithms (DFS and BFS) Algorithms for generating permutations, subsets Decrease by a constant factor (usually by half) Binary search Fake-coin problem Russian peasant multiplication Josephus problem Variable-size decrease Euclids algorithm The kth smallest element find algorithm Interpolation search,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Whats the difference? (example),Brute Force:,Consider the problem of exponentiation: an,Divide and conquer:,Decrease by one:,Decrease by constant factor:,The Application of Decrease by a constant factor technique,Search problem The binary search (S4.3, P135-139) Numerical problem Russian peasant multiplication (S5.5) Combinatorial problem Fake-coin problem (S5.5) Josephus problem (S5.5),2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Binary Search (basic idea),If the key is larger than the middle element, the key must be in the second half,r1 rmid-1 rmid rmid+1 rn,k,k rmid,k rmid,（mid=(1+n)/2）, , ,Used with a sorted list (the list is in increasing order),First check the middle list element,If the key matches the middle element, we are done,If the key is smaller than the middle element, the key must be in the first half,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Binary search example：Find the key value 14,0 1 2 3 4 5 6 7 8 9 10 11 12,3 14 27 31 39 42 55 70 74 81 85 93 98,5514,2714,314,14=14,2019/6/21,10,2012-2013-01 Design and Analysis of Algorithm SCUN,The Binary Search Algorithm,BinarySearchNR(A0n-1, K) /Input: An array A sorted in ascending order and a search K /Output: An index of the arrays element that is equal to K or -1 if there is no such element l 0; r n-1 while l r do m (l+r)/2 if K = Am return m else if K Am r m-1 else l m+1 return -1,Thinking: How to rewrite this algorithm in recursive format?,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,Best-case Analysis,The input instances in which the target matches the middle element will lead to the best case.,This means only one comparison is done. So we get: Tbest (n) = (1),2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Worst-Case Analysis,In the worst case, we will either find the element on the last pass, or not find the element at all,In each pass, only need 1 comparison. Hence, if we knew how many passes it has done, worst case is trivial,If n = 2k-1, then there must be k = log(n+1) passes,So, informally, we get: Tworst(n) = O(logn),If n is an arbitrary positive integer n, since after one pass, the algorithm faces the same situation but for an array half the size, we get the following recurrence relation for Tworst(n): Tworst(n) = Tworst ( n/2 ) + 1 n1 Tworst(1) = 1,So, formally: Tworst(n) = logn + 1 = log(n+1) = O(logn),2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Average-Case Analysis,Successful Search If the search is always successful, there are n places (number of possible keys) the key could be found We will consider each of these to be equivalent and so will give each a probability of 1/n There is one place we check on the first pass, two places we could check on the second pass, and four places we could check on the third pass, and so on.,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Average-Case Analysis (cont.),So we can represent binary search as a binary tree:,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Average-Case Analysis (cont.),In looking at the binary tree, we see that there are i comparisons needed to find the elements that are in the nodes of level i There are 2i-1 nodes on level i For a list with n = 2k-1 elements, there are k levels in the binary tree,The above facts give us:,2019/6/21,16,2012-2013-