The algorithm relies on a helper to find theĬrossing subarray. Recursion will handle the lower and upper halves. The strategy works because any subarray must lie in one of these three positions: Pseudocode The three (the subarray crossing the midpoint and the best of the solutions in the Conquer step). Combine by also finding a maximum subarray that crosses the midpoint, and using the best solution of Conquer by finding a maximum subarray of A and A[ mid+1 The solution strategy, given an array A, is: Divide the subarray into two subarrays of equal size as possible by finding the midpoint mid of The following algorithm is not the fastest known (a linear solution exists), but it illustratesĭivide and conquer. (The problem is trival unless there are negative numbers involved.) Suppose you have an array of numbers and need to find the subarray with the maximum sum ofĮlements in the subarray. We will get to them in a minute.įirst, let's take a look at another example of an algorithm that utilizes the Divide & Conquer strategy. There are several methods to solving recurrences of this form. Combine (line 5): Merging an n-element subarray takes Θ( n) (this term.Conquer (lines 3 and 4): 2 T( n/2) is required to recursively solve two.Divide (line 2): Θ(1) is required to compute q as the average of p.Power of 2, which gives us an upper bound on a tighter Θ analysis.) When (We can always raise a given n to the next Size n/ bcan be expressed as: Recurrence Analysis of Merge Sort Then the total time to solve a problem of size n by dividing into a problems of We also pay cost aT(n/b) solving subproblems. We pay cost D(n) to divide the problems and C(n) to combine the.Otherwise we divide the problem into a subproblems, eachġ/b size of the original.Problem directly with brute force or trivially in Θ(1) time. If n is below some constant (or often, n=1), we can solve the.Let T(n) be the running time on a problem of size n. Recurrence equations are used to describe the run time of Divide & ConquerĪlgorithms. Loop (line 12) makes n iterations, each taking constant time, for Θ( n) Analysis of MergeĪnalysis of the Merge procedure is straightforward. Merge Sort provides us with our first example of using recurrence relationsĪnd recursion trees for analysis. Used to show that Merge-Sort is correct for any N.Īnalysis of Merge Sort: Recurrence Relations and Recursion Tree Once correctness of Merge is established, induction can be Since the loop is rather straightforward, we will leave it to theĪbove example. Entries in L and R with slashes have been copied back into A.Ī loop invariant is used in the book to establish correctness of the Merge Entries with slashes have had their values copied to either L or R and have not Here's an example of how the final pass of MERGE(9, 12, 16) happens in an array, Now let's look in detail at the merge procedure, implemented using ∞ as sentinels (what do lines 1-2 do? lines 3-9 ? lines 10-17?): Here are examples when the input is a power of two, and another example when it is not a power of The strategy can be written simply and elegantly in recursive code. Picking the next smallest one off to place face-down in a new pile to make (This is like taking two decks of sorted cards and The subarrays from the smallest element up to copy the next smallest element Combine: Merge the two sorted subarrays with a (linear) procedure Merge that iterates over If they are singletons, we have theīase case. Conquer: Recursively sort the two subarrays. Merge Sort (which you should have seen in ICS 211 (Complex Sorting Algorithms)) takes this strategy: Divide: Given A, split the given array into two subarrays A and A[ q+1 If the subproblems are smallĮnough, solve them trivially or by "brute force." Combine the subproblem solutions to give a solution to the original problem. Conquer the subproblems by solving them recursively. Another strategy which is very powerfull is to Divide and Conquer: Divide the problem into subproblems that are smaller instances of the same problem. In the case of the Insertion Sort we saw Incremental Strategy for designing algorithms. The recursive nature of D&C leads to recurrences, or functions defined in terms CLRS Sections 2.3, 4.1, 4.3, 4.4, 4.5 (Sections 4.2 and 4.6 are optional, but may help you understand the material better)ĭivide & Conquer and Recurrences Divide & Conquer Strategy Divide the problem into subproblems that are smaller instances of the same problem.Analysis of Merge Sort: Recurrence Relations and Recursion Tree.Brief Comment on Merge Sort Correctness.Merge Sort: A Divide & Conquer Strategy.ICS 311 #7: Divide & Conquer and Analysis of Recurrences
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |