Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 17
Текст из файла (страница 17)
The analysis is broken into three lemmas. The first reduces the problem ofsolving the master recurrence to the problem of evaluating an expression that contains asummation. The second determines bounds on this summation. The third lemma puts the firsttwo together to prove a version of the master theorem for the case in which n is an exactpower of b.Lemma 4.2Let a ≥ 1 and b > 1 be constants, and let f (n) be a nonnegative function defined on exactpowers of b. Define T (n) on exact powers of b by the recurrencewhere i is a positive integer. Then(4.6)Proof We use the recursion tree in Figure 4.3. The root of the tree has cost f (n), and it has achildren, each with cost f (n/b).
(It is convenient to think of a as being an integer, especiallywhen visualizing the recursion tree, but the mathematics does not require it.) Each of thesechildren has a children with cost f (n/b2), and thus there are a2 nodes that are distance 2 fromthe root. In general, there are aj nodes that are distance j from the root, and each has cost f(n/bj). The cost of each leaf is T (1) = Θ(1), and each leaf is at depth logb n, since.There areleaves in the tree.Figure 4.3: The recursion tree generated by T (n) = aT (n/b) + f (n). The tree is a complete aary tree withleaves and height logb n. The cost of each level is shown at the right, andtheir sum is given in equation (4.6).We can obtain equation (4.6) by summing the costs of each level of the tree, as shown in thefigure.
The cost for a level j of internal nodes is aj f(n/bj), and so the total of all internal nodelevels isIn the underlying divide-and-conquer algorithm, this sum represents the costs of dividingproblems into subproblems and then recombining the subproblems. The cost of all the leaves,which is the cost of doing allsubproblems of size 1, is.In terms of the recursion tree, the three cases of the master theorem correspond to cases inwhich the total cost of the tree is (1) dominated by the costs in the leaves, (2) evenlydistributed across the levels of the tree, or (3) dominated by the cost of the root.The summation in equation (4.6) describes the cost of the dividing and combining steps in theunderlying divide-and-conquer algorithm.
The next lemma provides asymptotic bounds on thesummation's growth.Lemma 4.3Let a ≥ 1 and b > 1 be constants, and let f(n) be a nonnegative function defined on exactpowers of b. A function g(n) defined over exact powers of b by(4.7)can then be bounded asymptotically for exact powers of b as follows.1. Iffor some constant > 0, then.2.
If, then.3. If af (n/b) ≤ cf(n) for some constant c < 1 and for all n ≥ b, then g(n) = Θ(f(n)).Proof For case 1, we haveSubstituting into equation (4.7) yields, which implies that.(4.8)We bound the summation within the O-notation by factoring out terms and simplifying, whichleaves an increasing geometric series:Since b and are constants, we can rewrite the last expression asSubstituting this expression for the summation in equation (4.8) yields.and case 1 is proved.Under the assumption thatfor case 2, we have thatSubstituting into equation (4.7) yields.(4.9)We bound the summation within the Θ as in case 1, but this time we do not obtain a geometricseries. Instead, we discover that every term of the summation is the same:Substituting this expression for the summation in equation (4.9) yieldsg(n) = (=(,and case 2 is proved.Case 3 is proved similarly. Since f(n) appears in the definition (4.7) of g(n) and all terms ofg(n) are nonnegative, we can conclude that g(n) = Ω(f(n)) for exact powers of b.
Under ourassumption that af(n/b) ≤ cf(n) for some constant c < 1 and all n ≥ b, we have f(n/b) ≤(c/a)f(n). Iterating j times, we have f(n/bj) ≤ (c/a)j f(n) or, equivalently, aj f(n/bj) ≤ cj f(n).Substituting into equation (4.7) and simplifying yields a geometric series, but unlike the seriesin case 1, this one has decreasing terms:since c is constant. Thus, we can conclude that g(n) = Θ(f(n)) for exact powers of b.
Case 3 isproved, which completes the proof of the lemma.We can now prove a version of the master theorem for the case in which n is an exact powerof b.Lemma 4.4Let a ≥ 1 and b > 1 be constants, and let f(n) be a nonnegative function defined on exactpowers of b. Define T(n) on exact powers of b by the recurrencewhere i is a positive integer. Then T(n) can be bounded asymptotically for exact powers of bas follows.1. Iffor some constant > 0, then.2. If, then.3. Iffor some constant > 0, and if af (n/b) ≤ cf(n) for some constant c <1 and all sufficiently large n, then T(n) = Θ(f(n)).Proof We use the bounds in Lemma 4.3 to evaluate the summation (4.6) from Lemma 4.2.For case 1, we haveT(n) ==,and for case 2,T(n) ==.For case 3,T(n) == Θ(f(n)),because.4.4.2 Floors and ceilingsTo complete the proof of the master theorem, we must now extend our analysis to thesituation in which floors and ceilings are used in the master recurrence, so that the recurrenceis defined for all integers, not just exact powers of b.
Obtaining a lower bound on(4.10)and an upper bound on(4.11)is routine, since the bound ⌈n/b⌉ ≥ n/b can be pushed through in the first case to yield thedesired result, and the bound ⌊n/b⌋ ≤ n/b can be pushed through in the second case.
Lowerbounding the recurrence (4.11) requires much the same technique as upper bounding therecurrence (4.10), so we shall present only this latter bound.We modify the recursion tree of Figure 4.3 to produce the recursion tree in Figure 4.4. As wego down in the recursion tree, we obtain a sequence of recursive invocations on the argumentsFigure 4.4: The recursion tree generated by T(n) = aT(⌈n/b⌉) + f(n).
The recursive argumentnj is given by equation (4.12).n ,⌈n/b⌉ ,⌈⌈n/b⌉/b⌉ ,⌈⌈⌈n/b⌉/b⌉/b⌉ ,⋮Let us denote the jth element in the sequence by nj, where(4.12)Our first goal is to determine the depth k such that nk is a constant. Using the inequality ⌈x⌉ ≤x + 1, we obtainIn general,Letting j = ⌊logb n⌋, we obtainand thus we see that at depth ⌊logb n⌋, the problem size is at most a constant.From Figure 4.4, we see that(4.13)which is much the same as equation (4.6), except that n is an arbitrary integer and notrestricted to be an exact power of b.We can now evaluate the summation(4.14)from (4.13) in a manner analogous to the proof of Lemma 4.3.
Beginning with case 3, ifaf(⌈n/b⌉) ≤ cf(n) for n > b + b/(b - 1), where c < 1 is a constant, then it follows that ajf(nj) ≤cjf(n). Therefore, the sum in equation (4.14) can be evaluated just as in Lemma 4.3. For case. If we can show that, then the proof for2, we havecase 2 of Lemma 4.3 will go through. Observe that j = ≤ ⌊logb n⌋ implies bj/n ≤ 1. The boundimplies that there exists a constant c > 0 such that for all sufficiently large nj,sinceis a constant. Thus, case 2 is proved. The proof of case 1 is almostidentical. The key is to prove the bound, which is similar to the correspondingproof of case 2, though the algebra is more intricate.We have now proved the upper bounds in the master theorem for all integers n. The proof ofthe lower bounds is similar.Exercises 4.4-1:Give a simple and exact expression for nj in equation (4.12) for the case in which b is apositive integer instead of an arbitrary real number.Exercises 4.4-2:Show that if, where k ≥ 0, then the master recurrence has solution.
For simplicity, confine your analysis to exact powers of b.Exercises 4.4-3:Show that case 3 of the master theorem is overstated, in the sense that the regularity conditionaf(n/b) ≤ cf(n) for some constant c < 1 implies that there exists a constant > 0 such that.Problems 4-1: Recurrence examplesGive asymptotic upper and lower bounds for T(n) in each of the following recurrences.Assume that T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify youranswers.a.b.c.d.e.f.g.h.T(n) = 2T(n/2) + n3.T(n) = T(9n/10) + n.T(n) = 16T(n/4) + n2.T (n) = 7T(n/3) + n2.T(n) = 7T(n/2) + n2..T(n) = T(n - 1) + n..Problems 4-2: Finding the missing integerAn array A[1 n] contains all the integers from 0 to n except one. It would be easy todetermine the missing integer in O(n) time by using an auxiliary array B[0 n] to recordwhich numbers appear in A. In this problem, however, we cannot access an entire integer in Awith a single operation.
The elements of A are represented in binary, and the only operationwe can use to access them is "fetch the jth bit of A[i]," which takes constant time.Show that if we use only this operation, we can still determine the missing integer in O(n)time.Problems 4-3: Parameter-passing costsThroughout this book, we assume that parameter passing during procedure calls takesconstant time, even if an N-element array is being passed.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
