Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 9
Текст из файла (страница 9)
This empty subarray contains the k - p = 0 smallestelements of L and R, and since i = j = 1, both L[i] and R[j] are the smallest elements oftheir arrays that have not been copied back into A.•Maintenance: To see that each iteration maintains the loop invariant, let us firstsuppose that L[i] ≤ R[j]. Then L[i] is the smallest element not yet copied back into A.Because A[p k - 1] contains the k - p smallest elements, after line 14 copies L[i] intoA[k], the subarray A[p k] will contain the k - p + 1 smallest elements.
Incrementingk (in the for loop update) and i (in line 15) reestablishes the loop invariant for the next•iteration. If instead L[i] > R[j], then lines 16-17 perform the appropriate action tomaintain the loop invariant.Termination: At termination, k = r + 1. By the loop invariant, the subarray A[p k 1], which is A[p r], contains the k - p = r - p + 1 smallest elements of L[1 n1 + 1]and R[1 n2 + 1], in sorted order.
The arrays L and R together contain n1 + n2 + 2 = r- p + 3 elements. All but the two largest have been copied back into A, and these twolargest elements are the sentinels.To see that the MERGE procedure runs in Θ(n) time, where n = r - p + 1, observe that each oflines 1-3 and 8-11 takes constant time, the for loops of lines 4-7 take Θ(n1 + n2) = Θ(n)time,[6] and there are n iterations of the for loop of lines 12-17, each of which takes constanttime.We can now use the MERGE procedure as a subroutine in the merge sort algorithm. Theprocedure MERGE-SORT(A, p, r) sorts the elements in the subarray A[p r]. If p ≥ r, thesubarray has at most one element and is therefore already sorted.
Otherwise, the divide stepsimply computes an index q that partitions A[p r] into two subarrays: A[p q], containing⌈n/2⌉ elements, and A[q + 1r], containing ⌊n/2⌋ elements.[7]MERGE-SORT(A, p, r)1 if p < r2345then q ← ⌊(p + r)/2⌋MERGE-SORT(A, p, q)MERGE-SORT(A, q + 1, r)MERGE(A, p, q, r)To sort the entire sequence A = A[1], A[2], . . . , A[n] , we make the initial call MERGESORT(A, 1, length[A]), where once again length[A] = n. Figure 2.4 illustrates the operation ofthe procedure bottom-up when n is a power of 2. The algorithm consists of merging pairs of1-item sequences to form sorted sequences of length 2, merging pairs of sequences of length 2to form sorted sequences of length 4, and so on, until two sequences of length n/2 are mergedto form the final sorted sequence of length n.Figure 2.4: The operation of merge sort on the array A = 5, 2, 4, 7, 1, 3, 2, 6 .
The lengthsof the sorted sequences being merged increase as the algorithm progresses from bottom to top.2.3.2 Analyzing divide-and-conquer algorithmsWhen an algorithm contains a recursive call to itself, its running time can often be describedby a recurrence equation or recurrence, which describes the overall running time on aproblem of size n in terms of the running time on smaller inputs. We can then usemathematical tools to solve the recurrence and provide bounds on the performance of thealgorithm.A recurrence for the running time of a divide-and-conquer algorithm is based on the threesteps of the basic paradigm. As before, we let T (n) be the running time on a problem of sizen.
If the problem size is small enough, say n ≤ c for some constant c, the straightforwardsolution takes constant time, which we write as Θ(1). Suppose that our division of theproblem yields a subproblems, each of which is 1/b the size of the original. (For merge sort,both a and b are 2, but we shall see many divide-and-conquer algorithms in which a ≠ b.) Ifwe take D(n) time to divide the problem into subproblems and C(n) time to combine thesolutions to the subproblems into the solution to the original problem, we get the recurrenceIn Chapter 4, we shall see how to solve common recurrences of this form.Analysis of merge sortAlthough the pseudocode for MERGE-SORT works correctly when the number of elements isnot even, our recurrence-based analysis is simplified if we assume that the original problemsize is a power of 2.
Each divide step then yields two subsequences of size exactly n/2. InChapter 4, we shall see that this assumption does not affect the order of growth of the solutionto the recurrence.We reason as follows to set up the recurrence for T (n), the worst-case running time of mergesort on n numbers. Merge sort on just one element takes constant time. When we have n > 1elements, we break down the running time as follows.•••Divide: The divide step just computes the middle of the subarray, which takesconstant time. Thus, D(n) = Θ(1).Conquer: We recursively solve two subproblems, each of size n/2, which contributes2T (n/2) to the running time.Combine: We have already noted that the MERGE procedure on an n-elementsubarray takes time Θ(n), so C(n) = Θ(n).When we add the functions D(n) and C(n) for the merge sort analysis, we are adding afunction that is Θ(n) and a function that is Θ(1).
This sum is a linear function of n, that is,Θ(n). Adding it to the 2T (n/2) term from the "conquer" step gives the recurrence for theworst-case running time T (n) of merge sort:(2.1)In Chapter 4, we shall see the "master theorem," which we can use to show that T (n) is Θ(n lgn), where lg n stands for log2 n. Because the logarithm function grows more slowly than anylinear function, for large enough inputs, merge sort, with its Θ(n lg n) running time,outperforms insertion sort, whose running time is Θ(n2), in the worst case.We do not need the master theorem to intuitively understand why the solution to therecurrence (2.1) is T (n) = Θ(n lg n). Let us rewrite recurrence (2.1) as(2.2)where the constant c represents the time required to solve problems of size 1 as well as thetime per array element of the divide and combine steps.[8]Figure 2.5 shows how we can solve the recurrence (2.2).
For convenience, we assume that n isan exact power of 2. Part (a) of the figure shows T (n), which in part (b) has been expandedinto an equivalent tree representing the recurrence. The cn term is the root (the cost at the toplevel of recursion), and the two subtrees of the root are the two smaller recurrences T (n/2).Part (c) shows this process carried one step further by expanding T (n/2). The cost for each ofthe two subnodes at the second level of recursion is cn/2. We continue expanding each nodein the tree by breaking it into its constituent parts as determined by the recurrence, until theproblem sizes get down to 1, each with a cost of c.
Part (d) shows the resulting tree.Figure 2.5: The construction of a recursion tree for the recurrence T(n) = 2T(n/2) + cn. Part(a) shows T(n), which is progressively expanded in (b)-(d) to form the recursion tree. Thefully expanded tree in part (d) has lg n + 1 levels (i.e., it has height lg n, as indicated), andeach level contributes a total cost of cn. The total cost, therefore, is cn lg n + cn, which is Θ(nlg n).Next, we add the costs across each level of the tree.
The top level has total cost cn, the nextlevel down has total cost c(n/2) + c(n/2) = cn, the level after that has total cost c(n/4) + c(n/4)+ c(n/4) + c(n/4) = cn, and so on. In general, the level i below the top has 2i nodes, eachcontributing a cost of c(n/2i), so that the ith level below the top has total cost 2i c(n/2i) = cn.At the bottom level, there are n nodes, each contributing a cost of c, for a total cost of cn.The total number of levels of the "recursion tree" in Figure 2.5 is lg n + 1. This fact is easilyseen by an informal inductive argument. The base case occurs when n = 1, in which case thereis only one level.
Since lg 1 = 0, we have that lg n + 1 gives the correct number of levels.Now assume as an inductive hypothesis that the number of levels of a recursion tree for 2inodes is lg 2i + 1 = i + 1 (since for any value of i, we have that lg 2i = i). Because we areassuming that the original input size is a power of 2, the next input size to consider is 2i+1.
Atree with 2i+1 nodes has one more level than a tree of 2i nodes, and so the total number oflevels is (i + 1) + 1 = lg 2i+1 + 1.To compute the total cost represented by the recurrence (2.2), we simply add up the costs ofall the levels. There are lg n + 1 levels, each costing cn, for a total cost of cn(lg n + 1) = cn lgn + cn. Ignoring the low-order term and the constant c gives the desired result of Θ(n lg n).Exercises 2.3-1Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A =52, 26, 38, 57, 9, 49 .3, 41,Exercises 2.3-2Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once eitherarray L or R has had all its elements copied back to A and then copying the remainder of theother array back into A.Exercises 2.3-3Use mathematical induction to show that when n is an exact power of 2, the solution of therecurrenceExercises 2.3-4Insertion sort can be expressed as a recursive procedure as follows.
In order to sort A[1 n],we recursively sort A[1 n -1] and then insert A[n] into the sorted array A[1 n - 1]. Write arecurrence for the running time of this recursive version of insertion sort.Exercises 2.3-5Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A issorted, we can check the midpoint of the sequence against v and eliminate half of thesequence from further consideration. Binary search is an algorithm that repeats thisprocedure, halving the size of the remaining portion of the sequence each time. Writepseudocode, either iterative or recursive, for binary search.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
