Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 98
Текст из файла (страница 98)
In thissection, we shall examine the function α to see just how slowly it grows. Then we prove thisrunning time using the potential method of amortized analysis.A very quickly growing function and its very slowly growing inverseFor integers k ≥ 0 and j ≥ 1, we define the function Ak(j) aswhere the expressionSpecifically,andlevel of the function A.uses the functional-iteration notation given in Section 3.2.for i ≥ 1.
We will refer to the parameter k as theThe function Ak(j) strictly increases with both j and k. To see just how quickly this functiongrows, we first obtain closed-form expressions for A1(j) and A2(j).Lemma 21.2For any integer j ≥ 1, we have A1(j) = 2 j + 1.Proof We first use induction on i to show that. For the base case, we have. For the inductive step, assume that. Then. Finally, we note that.Lemma 21.3For any integer j ≥ 1, we have A2(j) = 2j+1(j + 1) - 1.Proof We first use induction on i to show that. For the inductive step, assume thatthat.
For the base case, we have. Then. Finally, we note.Now we can see how quickly Ak(j) grows by simply examining Ak (1) for levels k = 0, 1, 2, 3,4. From the definition of A0(k) and the above lemmas, we have A0(1) = 1 + 1 = 2, A1(1) = 2 · 1+ 1 = 3, and A2(1) = 21+1 · (1 + 1) - 1 = 7. We also haveA3(1) == A2(A2(1))= A2(7)= 28 · 8 - 1= 211 - 1= 2047andA4(1) == A3(A3(1))= A3(2047)=A2(2047)= 12048· 2048 - 1> 22048= (24)512= 165121080,which is the estimated number of atoms in the observable universe.We define the inverse of the function Ak (n), for integer n ≥ 0, byα(n) = min {k : Ak(1) = n} .In words, α(n) is the lowest level k for which Ak(1) is at least n.
From the above values ofAk(1), we see thatIt is only for impractically large values of n (greater than A4(1), a huge number) that α(n) > 4,and so α(n) ≤ 4 for all practical purposes.Properties of ranksIn the remainder of this section, we prove an O(m α(n)) bound on the running time of thedisjoint-set operations with union by rank and path compression. In order to prove this bound,we first prove some simple properties of ranks.Lemma 21.4For all nodes x, we have rank[x] ≤ rank[p[x]], with strict inequality if x ≠ p[x]. The value ofrank[x] is initially 0 and increases through time until x ≠ p[x]; from then on, rank[x] does notchange.
The value of rank[p[x]] monotonically increases over time.Proof The proof is a straightforward induction on the number of operations, using theimplementations of MAKE-SET, UNION, and FIND-SET that appear in Section 21.3. Weleave it as Exercise 21.4-1.Corollary 21.5As we follow the path from any node toward a root, the node ranks strictly increase.Lemma 21.6Every node has rank at most n - 1.Proof Each node's rank starts at 0, and it increases only upon LINK operations. Because thereare at most n - 1 UNION operations, there are also at most n - 1 LINK operations.
Becauseeach LINK operation either leaves all ranks alone or increases some node's rank by 1, allranks are at most n - 1.Lemma 21.6 provides a weak bound on ranks. In fact, every node has rank at most ⌊lg n⌋ (seeExercise 21.4-2). The looser bound of Lemma 21.6 will suffice for our purposes, however.Proving the time boundWe shall use the potential method of amortized analysis (see Section 17.3) to prove theO(mα(n)) time bound.
In performing the amortized analysis, it is convenient to assume thatwe invoke the LINK operation rather than the UNION operation. That is, since the parametersof the LINK procedure are pointers to two roots, we assume that the appropriate FIND-SEToperations are performed separately.
The following lemma shows that even if we count theextra FIND-SET operations induced by UNION calls, the asymptotic running time remainsunchanged.Lemma 21.7Suppose we convert a sequence S' of m' MAKE-SET, UNION, and FIND-SET operations intoa sequence S of m MAKE-SET, LINK, and FIND-SET operations by turning each UNIONinto two FIND-SET operations followed by a LINK. Then, if sequence S runs in O(m α(n))time, sequence S' runs in O(m' α(n)) time.Proof Since each UNION operation in sequence S' is converted into three operations in S, wehave m' ≤ m ≤ 3m'.
Since m = O(m'), an O(m α(n)) time bound for the converted sequence Simplies an O(m' α(n)) time bound for the original sequence S'.In the remainder of this section, we shall assume that the initial sequence of m' MAKE-SET,UNION, and FIND-SET operations has been converted to a sequence of m MAKE-SET,LINK, and FIND-SET operations. We now prove an O(m α(n)) time bound for the convertedsequence and appeal to Lemma 21.7 to prove the O(m' α(n)) running time of the originalsequence of m' operations.Potential functionThe potential function we use assigns a potential φq(x) to each node x in the disjoint-set forestafter q operations.
We sum the node potentials for the potential of the entire forest: Φq = Σxφ(x), where Φq denotes the potential of the forest after q operations. The forest is empty prior tothe first operation, and we arbitrarily set Φ0 = 0. No potential Φq will ever be negative.The value of φq(x) depends on whether x is a tree root after the qth operation. If it is, or ifrank[x] = 0, then φq(x) = α(n) · rank[x].Now suppose that after the qth operation, x is not a root and that rank[x] ≥ 1.
We need todefine two auxiliary functions on x before we can define φq(x). First we definelevel(x) = max {k : rank[p[x]] ≥ Ak (rank[x])} .That is, level(x) is the greatest level k for which Ak, applied to x's rank, is no greater than x'sparent's rank.We claim that(21.1)which we see as follows. We haverank[p[x]] ≥ rank[x] + 1 (by Lemma 21.4)= A0(rank[x]) (by definition of A0(j)) ,which implies that level(x) ≥ 0, and we haveAα(n)(rank[x]) ≥ Aα(n)(1) (because Ak(j) is strictly increasing)≥n(by the definition of α(n))> rank[p[x]] (by Lemma 21.6) ,which implies that level(x) < α(n).
Note that because rank[p[x]] monotonically increases overtime, so does level(x).The second auxiliary function isThat is, iter(x) is the largest number of times we can iteratively apply Alevel(x), applied initiallyto x's rank, before we get a value greater than x's parent's rank.We claim that(21.2)which we see as follows. We havewhich implies that iter(x) ≥ 1, and we havewhich implies that iter(x) ≤ rank[x]. Note that because rank[p[x]] monotonically increasesover time, in order for iter(x) to decrease, level(x) must increase. As long as level(x) remainsunchanged, iter(x) must either increase or remain unchanged.With these auxiliary functions in place, we are ready to define the potential of node x after qoperations:The next two lemmas give useful properties of node potentials.Lemma 21.8For every node x, and for all operation counts q, we have0 ≤ φq(x) ≤ α(n) · rank[x].Proof If x is a root or rank[x] = 0, then φq(x) = α(n) · rank[x] by definition.
Now suppose thatx is not a root and that rank[x] ≥ 1. We obtain a lower bound on φq(x) by maximizing level(x)and iter(x). By the bound (21.1), level(x) ≤ α(n) - 1, and by the bound (21.2), iter(x) ≤ rank[x].Thus,φq(x) ≥ (α(n) - (α(n) - 1)) · rank[x] - rank[x]= rank[x] - rank[x]= 0.Similarly, we obtain an upper bound on φq(x) by minimizing level(x) and iter(x). By the bound(21.1), level(x) ≥ 0, and by the bound (21.2), iter(x) ≥ 1. Thus,φq(x) ≤ (α(n) - 0) · rank[x] 1= α(n) · rank[x] - 1< α(n) · rank[x].Potential changes and amortized costs of operationsWe are now ready to examine how the disjoint-set operations affect node potentials. With anunderstanding of the change in potential due to each operation, we can determine eachoperation's amortized cost.Lemma 21.9Let x be a node that is not a root, and suppose that the qth operation is either a LINK orFIND-SET.
Then after the qth operation, φq(x) ≤ φq-1(x). Moreover, if rank[x] ≥ 1 and eitherlevel(x) or iter(x) changes due to the qth operation, then φq(x) ≤ φq-1(x) - 1. That is, x'spotential cannot increase, and if it has positive rank and either level(x) or iter(x) changes, thenx's potential drops by at least 1.Proof Because x is not a root, the qth operation does not change rank[x], and because n doesnot change after the initial n MAKE-SET operations, α(n) remains unchanged as well. Hence,these components of the formula for x's potential remain the same after the qth operation. Ifrank[x] = 0, then φq(x) = φq-1(x) = 0. Now assume that rank[x] ≥ 1.Recall that level(x) monotonically increases over time.
If the qth operation leaves level(x)unchanged, then iter(x) either increases or remains unchanged. If both level(x) and iter(x) areunchanged, then φq(x) = φq-1(x). If level(x) is unchanged and iter(x) increases, then it increasesby at least 1, and so φq(x) ≤ φq-1(x) - 1.Finally, if the qth operation increases level(x), it increases by at least 1, so that the value of theterm (α(n) - level(x)) · rank[x] drops by at least rank[x]. Because level(x) increased, the valueof iter(x) might drop, but according to the bound (21.2), the drop is by at most rank[x] - 1.Thus, the increase in potential due to the change in iter(x) is less than the decrease in potentialdue to the change in level(x), and we conclude that φq(x) ≤ φq-1(x) - 1.Our final three lemmas show that the amortized cost of each MAKE-SET, LINK, and FINDSET operation is O(α(n)).
Recall from equation (17.2) that the amortized cost of eachoperation is its actual cost plus the increase in potential due to the operation.Lemma 21.10The amortized cost of each MAKE-SET operation is O(1).Proof Suppose that the qth operation is MAKE-SET(x). This operation creates node x withrank 0, so that φq(x) = 0. No other ranks or potentials change, and so Φq = Φq-1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
