Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

For example, in the recurrence (4.4) we canfalsely "prove" T (n) = O(n) by guessing T (n) ≤ cn and then arguingT (n) ≤ 2(c ⌊n/2⌋) + n≤ cn + n= O(n) , ⇐wrong!!since c is a constant. The error is that we haven't proved the exact form of the inductivehypothesis, that is, that T (n) ≤ cn.Changing variablesSometimes, a little algebraic manipulation can make an unknown recurrence similar to oneyou have seen before. As an example, consider the recurrencewhich looks difficult. We can simplify this recurrence, though, with a change of variables.

Forconvenience, we shall not worry about rounding off values, such as , to be integers.Renaming m = lg n yieldsT (2m) = 2T (2m/2) + m.We can now rename S(m) = T(2m) to produce the new recurrenceS(m) = 2S(m/2) + m,which is very much like recurrence (4.4). Indeed, this new recurrence has the same solution:S(m) = O(m lg m).

Changing back from S(m) to T (n), we obtain T (n) = T (2m) = S(m) = O(mlg m) = O(lg n lg lg n).Exercises 4.1-1Show that the solution of T (n) = T (⌈n/2⌉) + 1 is O(lg n).Exercises 4.1-2We saw that the solution of T (n) = 2T (⌊n/2⌋) + n is O(n lg n). Show that the solution of thisrecurrence is also Ω(n lg n). Conclude that the solution is Θ(n lg n).Exercises 4.1-3Show that by making a different inductive hypothesis, we can overcome the difficulty withthe boundary condition T (1) = 1 for the recurrence (4.4) without adjusting the boundaryconditions for the inductive proof.Exercises 4.1-4Show that Θ(n lg n) is the solution to the "exact" recurrence (4.2) for merge sort.Exercises 4.1-5Show that the solution to T (n) = 2T (⌊n/2⌋ + 17) + n is O(n lg n).Exercises 4.1-6Solve the recurrenceby making a change of variables.

Your solution should beasymptotically tight. Do not worry about whether values are integral.4.2 The recursion-tree methodAlthough the substitution method can provide a succinct proof that a solution to a recurrenceis correct, it is sometimes difficult to come up with a good guess. Drawing out a recursiontree, as we did in our analysis of the merge sort recurrence in Section 2.3.2, is astraightforward way to devise a good guess. In a recursion tree, each node represents the costof a single subproblem somewhere in the set of recursive function invocations. We sum thecosts within each level of the tree to obtain a set of per-level costs, and then we sum all theper-level costs to determine the total cost of all levels of the recursion.

Recursion trees areparticularly useful when the recurrence describes the running time of a divide-and-conqueralgorithm.A recursion tree is best used to generate a good guess, which is then verified by thesubstitution method. When using a recursion tree to generate a good guess, you can oftentolerate a small amount of "sloppiness," since you will be verifying your guess later on. If youare very careful when drawing out a recursion tree and summing the costs, however, you canuse a recursion tree as a direct proof of a solution to a recurrence. In this section, we will userecursion trees to generate good guesses, and in Section 4.4, we will use recursion treesdirectly to prove the theorem that forms the basis of the master method.For example, let us see how a recursion tree would provide a good guess for the recurrence T(n) = 3T (⌊n/4⌋) + Θ(n2).

We start by focusing on finding an upper bound for the solution.Because we know that floors and ceilings are usually insubstantial in solving recurrences(here's an example of sloppiness that we can tolerate), we create a recursion tree for therecurrence T (n) = 3T(n/4) + cn2, having written out the implied constant coefficient c > 0.Figure 4.1 shows the derivation of the recursion tree for T (n) = 3T (n/4) + cn2. Forconvenience, we assume that n is an exact power of 4 (another example of tolerablesloppiness). Part (a) of the figure shows T (n), which is expanded in part (b) into an equivalenttree representing the recurrence. The cn2 term at the root represents the cost at the top level ofrecursion, and the three subtrees of the root represent the costs incurred by the subproblems ofsize n/4.

Part (c) shows this process carried one step further by expanding each node with costT (n/4) from part (b). The cost for each of the three children of the root is c(n/4)2. We continueexpanding each node in the tree by breaking it into its constituent parts as determined by therecurrence.Figure 4.1: The construction of a recursion tree for the recurrence T(n) = 3T(n/4) + cn2.

Part(a) shows T(n), which is progressively expanded in (b)-(d) to form the recursion tree. Thefully expanded tree in part (d) has height log4 n (it has log4 n + 1 levels).Because subproblem sizes decrease as we get further from the root, we eventually must reacha boundary condition. How far from the root do we reach one? The subproblem size for anode at depth i is n/4i. Thus, the subproblem size hits n = 1 when n/4i = 1 or, equivalently,when i = log4 n. Thus, the tree has log 4n + 1 levels (0, 1, 2,..., log4 n).Next we determine the cost at each level of the tree.

Each level has three times more nodesthan the level above, and so the number of nodes at depth i is 3i. Because subproblem sizesreduce by a factor of 4 for each level we go down from the root, each node at depth i, for i =0, 1, 2,..., log4 n - 1, has a cost of c(n/4i)2. Multiplying, we see that the total cost over all nodesat depth i, for i = 0, 1, 2,..., log4 n - 1, is 3i c(n/4i)2 = (3/16)i cn2. The last level, at depth log4 n,hasnodes, each contributing cost T (1), for a total cost of, which is.Now we add up the costs over all levels to determine the cost for the entire tree:This last formula looks somewhat messy until we realize that we can again take advantage ofsmall amounts of sloppiness and use an infinite decreasing geometric series as an upperbound.

Backing up one step and applying equation (A.6), we haveThus, we have derived a guess of T (n) = O(n2) for our original recurrence T (n) = 3T (⌊n/4⌋)+ Θ(n2). In this example, the coefficients of cn2 form a decreasing geometric series and, byequation (A.6), the sum of these coefficients is bounded from above by the constant 16/13.Since the root's contribution to the total cost is cn2, the root contributes a constant fraction ofthe total cost. In other words, the total cost of the tree is dominated by the cost of the root.In fact, if O(n2) is indeed an upper bound for the recurrence (as we shall verify in a moment),then it must be a tight bound. Why? The first recursive call contributes a cost of Θ(n2), and soΩ (n2) must be a lower bound for the recurrence.Now we can use the substitution method to verify that our guess was correct, that is, T (n) =O(n2) is an upper bound for the recurrence T (n) = 3T (⌊n/4⌋)+Θ(n2).

We want to show that T(n) ≤ dn2 for some constant d > 0. Using the same constant c > 0 as before, we haveT(n) ≤ 3T(⌊n/4⌋) + cn2≤ 3d⌊n/4⌋2 + cn2≤ 3d(n/4)2 + cn2= 3/16 dn2 + cn2≤ dn2,where the last step holds as long as d ≥ (16/13)c.As another, more intricate example, Figure 4.2 shows the recursion tree for T (n) = T(n/3) +T(2n/3) + O(n).Figure 4.2: A recursion tree for the recurrence T(n) = T (n/3) + T (2n/3) + cn.(Again, we omit floor and ceiling functions for simplicity.) As before, we let c represent theconstant factor in the O(n) term.

When we add the values across the levels of the recursiontree, we get a value of cn for every level. The longest path from the root to a leaf is n →(2/3)n → (2/3)2n → ··· → 1. Since (2/3)kn = 1 when k = log3/2 n, the height of the tree is log3/2n.Intuitively, we expect the solution to the recurrence to be at most the number of levels timesthe cost of each level, or O(cn log3/2 n) = O(n lg n). The total cost is evenly distributedthroughout the levels of the recursion tree. There is a complication here: we have yet toconsider the cost of the leaves. If this recursion tree were a complete binary tree of heightlog3/2 n, there would beleaves. Since the cost of each leaf is a constant, the totalcost of all leaves would then be, which is ω(n lg n).

This recursion tree is not acomplete binary tree, however, and so it has fewer thanleaves. Moreover, as we go downfrom the root, more and more internal nodes are absent. Consequently, not all levelscontribute a cost of exactly cn; levels toward the bottom contribute less.

We could work outan accurate accounting of all costs, but remember that we are just trying to come up with aguess to use in the substitution method. Let us tolerate the sloppiness and attempt to show thata guess of O(n lg n) for the upper bound is correct.Indeed, we can use the substitution method to verify that O(n lg n) is an upper bound for thesolution to the recurrence.

Характеристики

Список файлов книги