《算法课件全121301ADA11减治法减可变规模算法》由会员分享，可在线阅读，更多相关《算法课件全121301ADA11减治法减可变规模算法（20页珍藏版）》请在金锄头文库上搜索。
1、Decrease and Conquer (III),Chapter 5,Variable-Size-Decrease Algorithms Selection Problem The kth smallest element find problem Search Problem Interpolation Search Combinatory Problem The game of Nim,2019/6/22,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of thi
2、s lecture, you should Understand whats selection problem and master the partition based algorithm for finding the kth smallest elements Master the basic idea of interpolation search and know the differences between binary search and interpolation search Know how to solve the game of nim,2019/6/22,4,
3、2012-2013-01 Design and Analysis of Algorithm SCUN,Selection Problem,Whats selection problem?,Is to find a particular element of an unsorted list,Classical selection problem,Generally, find the kth smallest element,Find the maximum or minimum elements or the both,Find the median element The median i
4、s used in statistics as a measure of an average value of a sample. In fact, it is a better (more robust) indicator than the mean, which is used for the same purpose.,Example: 4, 1, 10, 9, 7, 12, 8, 2, 15 median = ?,2019/6/22,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Find the kth element (
5、direct idea),To find the kth smallest element, we could move the k smallest elements to the start of the list and then the kth smallest will be in location listk This involves finding the smallest element and moving it to the first place, then finding the second smallest element and moving it to the
6、 second place and so on,2019/6/22,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Direct Idea Algorithm,FindkthSmallestBF(A0n-1, k) /Input: An array A of orderable elements and integer k (1kn) /Output: The value of the kth smallest element in A0n-1 for i 0 to k-1 smallestLocation n-1 for j n-2
7、to i if Aj AsmallestLocation smallestLocation = j end if end for swap(Ai, AsmallestLocation) end for Return Ak-1,2019/6/22,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Direct Idea Algorithm Analysis,We need to do k passes, thus giving,On the first pass, we compare the last element to the res
8、t, doing n - 1 comparisons On the second pass, we compare the last element to the rest (except the first element), doing n - 2 comparisons, and so on,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithms based on Variable-Size-Decrease Technique,A faster algorithm is based on using the qui
9、cksort-like partition of the list. Let s be a split position obtained by a partition: Assuming that the list is indexed from 1 to n: If s = k, the problem is solved; if s k, look for the k-th smallest elem. in the left part; if s k, look for the (k-s)th smallest elem. in the right part.,Note: The sa
10、me idea can be implemented without recursion as well. For the non recursive version, we need not even adjust the value of k but just continue until s = k.,2019/6/22,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Tracing the Median / Selection Algorithm,Example: 4 1 10 9 7 12 8 2 15 Here: n = 9
11、, k = 9/2 = 5 array index 1 2 3 4 5 6 7 8 9 4 1 10 9 7 12 8 2 15 4 1 2 9 7 12 8 10 15 2 1 4 9 7 12 8 10 15 - s=3 k=5 8 7 7 8 - s=k=5,Solution: median is 8,2019/6/22,10,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithms based on variable-size-decrease technique,FindkthSmallestVSD_NR(A0n-1,
12、 k) /Input: An array A of orderable elements and integer k (1kn) /Output: The value of the kth smallest element in A0n-1 l 0; r n-1 While l r p Al; j l for i l +1 to r if Ai p j j + 1 if j i swap(Aj, Ai) swap(Al, Aj) if j k-1 r j-1 else if j k-1 l j+1 else return Ak-1,Partition algorithm,Thinking: H
13、ow to rewrite this algorithm in recursive format?,j partition2(A, l , r),/j partition2(A, l , r),2019/6/22,11,2012-2013-01 Design and Analysis of Algorithm SCUN,Best Case Analysis,The above recurrence works out to TB(n) = 2n 1 + logn = (n),So we can get the number of comparison recurrence relation,A
14、ccording to the Partition algorithm, if the list is divided in half each time, this will lead to the best case. The Partition Algorithm will do n-1 comparisons for a list of size n,2019/6/22,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Worst Case Analysis,The above recurrence works out to T
15、W(n) = (n+2)*k - k*(k+1)/2 = O(n*k),According to the Partition algorithm, if the list is divided by n-1 to 0, this will lead to the worst case. The Partition Algorithm will do n-1 comparisons for a list of size n,So we can get the number of comparison recurrence relation,2019/6/22,13,2012-2013-01 De
16、sign and Analysis of Algorithm SCUN,Average-Case Analysis,This would work out to TA(n)4n, so TA(n) = (n),So we can get,In each patition, there could be n places for the pivot for a list of size n, We will consider each of these to be equivalent and so will give each a probability of 1/n The Partition Al
