Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 16
Текст из файла (страница 16)
We show that T (n) ≤ dn lg n, where d is a suitable positiveconstant. We haveT(n) ≤ T(n/3) + T(2n/3) + cn≤ d(n/3)lg(n/3) + d(2n/3)lg(2n/3) + cn= (d(n/3)lgn - d(n/3)lg 3) + (d(2n/3) lg n - d(2n/3)lg(3/2)) + cn= dn lg n - d((n/3) lg 3 + (2n/3) lg(3/2)) + cn= dn lg n - d((n/3) lg 3 + (2n/3) lg 3 - (2n/3)lg 2) + cn= dn lg n - dn(lg 3 - 2/3) + cn≤ dn lg n,as long as d ≥ c/(lg 3 - (2/3)).
Thus, we did not have to perform a more accurate accounting ofcosts in the recursion tree.Exercises 4.2-1Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) =3T(⌊n/2⌋) + n. Use the substitution method to verify your answer.Exercises 4.2-2Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + cn, where c is a constant,is Ω(n lg n) by appealing to a recursion tree.Exercises 4.2-3Draw the recursion tree for T (n) = 4T (⌊n/2⌋)+cn, where c is a constant, and provide a tightasymptotic bound on its solution.
Verify your bound by the substitution method.Exercises 4.2-4Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n - a) +T(a) + cn, where a ≥ 1 and c > 0 are constants.Exercises 4.2-5Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) +T((1 - α)n) + cn, where α is a constant in the range 0 <α < 1 and c > 0 is also a constant.4.3 The master methodThe master method provides a "cookbook" method for solving recurrences of the form(4.5)where a ≥ 1 and b > 1 are constants and f (n) is an asymptotically positive function.
Themaster method requires memorization of three cases, but then the solution of manyrecurrences can be determined quite easily, often without pencil and paper.The recurrence (4.5) describes the running time of an algorithm that divides a problem of sizen into a subproblems, each of size n/b, where a and b are positive constants. The asubproblems are solved recursively, each in time T (n/b).
The cost of dividing the problemand combining the results of the subproblems is described by the function f (n). (That is, usingthe notation from Section 2.3.2, f(n) = D(n)+C(n).) For example, the recurrence arising fromthe MERGE-SORT procedure has a = 2, b = 2, and f (n) = Θ(n).As a matter of technical correctness, the recurrence isn't actually well defined because n/bmight not be an integer. Replacing each of the a terms T (n/b) with either T (⌊n/b⌋) or T(⌈n/b⌉) doesn't affect the asymptotic behavior of the recurrence, however. (We'll prove this inthe next section.) We normally find it convenient, therefore, to omit the floor and ceilingfunctions when writing divide-and-conquer recurrences of this form.The master theoremThe master method depends on the following theorem.Theorem 4.1: (Master theorem)Let a ≥ 1 and b > 1 be constants, let f (n) be a function, and let T (n) be defined on thenonnegative integers by the recurrenceT(n) = aT(n/b) + f(n),where we interpret n/b to mean either ⌊n/b⌋ or ⌈n/b⌉.
Then T (n) can be boundedasymptotically as follows.1. Iffor some constant > 0, then2. If, then.3. Iffor some constant > 0, and if a f (n/b) ≤ cf (n) for some constant c <1 and all sufficiently large n, then T (n) = Θ(f (n)).Before applying the master theorem to some examples, let's spend a moment trying tounderstand what it says. In each of the three cases, we are comparing the function f (n) withthe function.
Intuitively, the solution to the recurrence is determined by the larger of thetwo functions. If, as in case 1, the functionis the larger, then the solution is.If, as in case 3, the function f (n) is the larger, then the solution is T (n) = Θ(f (n)). If, as incase 2, the two functions are the same size, we multiply by a logarithmic factor, and thesolution is.Beyond this intuition, there are some technicalities that must be understood.
In the first case,not only must f (n) be smaller than, it must be polynomially smaller. That is, f (n) must beasymptotically smaller thanby a factor of n for some constant > 0. In the third case,not only must f (n) be larger than, it must be polynomially larger and in addition satisfythe "regularity" condition that af (n/b) ≤ cf(n). This condition is satisfied by most of thepolynomially bounded functions that we shall encounter.It is important to realize that the three cases do not cover all the possibilities for f (n). There isa gap between cases 1 and 2 when f (n) is smaller thanbut not polynomially smaller.Similarly, there is a gap between cases 2 and 3 when f (n) is larger thanbut notpolynomially larger. If the function f (n) falls into one of these gaps, or if the regularitycondition in case 3 fails to hold, the master method cannot be used to solve the recurrence.Using the master methodTo use the master method, we simply determine which case (if any) of the master theoremapplies and write down the answer.As a first example, considerT (n) = 9T(n/3) + n.For this recurrence, we have a = 9, b = 3, f (n) = n, and thus we have that.Since, where = 1, we can apply case 1 of the master theorem and concludethat the solution is T (n) = Θ(n2).Now considerT (n) = T (2n/3) + 1,in which a = 1, b = 3/2, f (n) = 1, and.
Case 2 applies, since, and thus the solution to the recurrence is T(n) = Θ(lg n).For the recurrenceT(n) = 3T(n/4) + n lg n,we have a = 3, b = 4, f (n) = n lg n, and. Since, where ≈ 0.2, case 3 applies if we can show that the regularity conditionholds for f (n). For sufficiently large n, af (n/b) = 3(n/4)lg(n/4) ≤ (3/4)n lg n = cf (n) for c =3/4. Consequently, by case 3, the solution to the recurrence is T(n) = Θ(nlg n).The master method does not apply to the recurrenceT(n) = 2T(n/2) + n lg n,even though it has the proper form: a = 2, b = 2, f(n) = n lg n, and. It might seem thatcase 3 should apply, since f (n) = n lg n is asymptotically larger than.
The problem isthat it is not polynomially larger. The ratiois asymptotically less thann for any positive constant . Consequently, the recurrence falls into the gap between case 2and case 3. (See Exercise 4.4-2 for a solution.)Exercises 4.3-1Use the master method to give tight asymptotic bounds for the following recurrences.a.
T (n) = 4T(n/2) + n.b. T (n) = 4T(n/2) + n2.c. T (n) = 4T(n/2) + n3.Exercises 4.3-2The recurrence T(n) = 7T (n/2)+n2 describes the running time of an algorithm A. A competingalgorithm A′ has a running time of T′(n) = aT′(n/4) + n2. What is the largest integer value for asuch that A′ is asymptotically faster than A?Exercises 4.3-3Use the master method to show that the solution to the binary-search recurrence T(n) = T (n/2)+ Θ(1) is T(n) = Θ(lg n). (See Exercise 2.3-5 for a description of binary search.)Exercises 4.3-4Can the master method be applied to the recurrence T (n) = 4T(n/2) + n2 lg n? Why or whynot? Give an asymptotic upper bound for this recurrence.Exercises 4.3-5:Consider the regularity condition af (n/b) ≤ cf(n) for some constant c < 1, which is part of case3 of the master theorem. Give an example of constants a ≥ 1 and b > 1 and a function f (n) thatsatisfies all the conditions in case 3 of the master theorem except the regularity condition.4.4: Proof of the master theoremThis section contains a proof of the master theorem (Theorem 4.1).
The proof need not beunderstood in order to apply the theorem.The proof is in two parts. The first part analyzes the "master" recurrence (4.5), under thesimplifying assumption that T(n) is defined only on exact powers of b > 1, that is, for n = 1, b,b2, .. This part gives all the intuition needed to understand why the master theorem is true.The second part shows how the analysis can be extended to all positive integers n and ismerely mathematical technique applied to the problem of handling floors and ceilings.In this section, we shall sometimes abuse our asymptotic notation slightly by using it todescribe the behavior of functions that are defined only over exact powers of b. Recall that thedefinitions of asymptotic notations require that bounds be proved for all sufficiently largenumbers, not just those that are powers of b.
Since we could make new asymptotic notationsthat apply to the set {bi : i = 0, 1,...}, instead of the nonnegative integers, this abuse is minor.Nevertheless, we must always be on guard when we are using asymptotic notation over alimited domain so that we do not draw improper conclusions. For example, proving that T (n)= O(n) when n is an exact power of 2 does not guarantee that T (n) = O(n).
The function T (n)could be defined asin which case the best upper bound that can be proved is T (n) = O(n2). Because of this sort ofdrastic consequence, we shall never use asymptotic notation over a limited domain withoutmaking it absolutely clear from the context that we are doing so.4.4.1 The proof for exact powersThe first part of the proof of the master theorem analyzes the recurrence (4.5)T (n) = aT (n/b) + f (n) ,for the master method, under the assumption that n is an exact power of b > 1, where b neednot be an integer.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
