chap22.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h2>Ackermann's function and its inverse</h2><P>
<a name="0897_1705"><a name="0897_1706">To understand Ackermann's function and its inverse <img src="../images/alpha12.gif">, it helps to have a notation for repeated exponentiation. For an integer <I>i</I> <img src="../images/gteq.gif"> 0, the expression<P>
<img src="450_a.gif"><P>
stands for the function <I>g</I>(<I>i</I>), defined recursively by<P>
<img src="450_b.gif"><P>
Intuitively, the parameter <I>i</I> gives the "height of the stack of 2's" that make up the exponent. For example,<P>
<img src="451_a.gif"><P>
<h4><a name="0897_170b">Figure 22.6 Values of A(i, j) for small values of i and j.<a name="0897_170b"></sub></sup></h4><P>
<img src="451_b.gif"><P>
<a name="0897_1707"><a name="0897_1708">Recall the definition of the function 1<I>g</I>* in terms of the functions lg<SUP>(<I>i</I>)</SUP> defined for integer <I>i</I> <img src="../images/gteq.gif"> 0:<P>
<img src="451_c.gif"><P>
The 1g* function is essentially the inverse of repeated exponentiation:<P>
<img src="451_d.gif"><P>
<a name="0897_1709">We are now ready to show Ackermann's function, which is defined for integers <I>i</I>, <I>j</I> <img src="../images/gteq.gif"> 1 by<P>
<pre><I>A</I>(1,<I>j</I>)  =  2<I><SUP>j</I></SUP>                   for <I>j</I> <img src="../images/gteq.gif"> 1 ,</sub></sup></pre><P>
<pre><I>A</I>(<I>i</I>,1)  =  <I>A</I>(<I>i</I> - 1,2)           for <I>i</I> <img src="../images/gteq.gif"> 2 ,</sub></sup></pre><P>
<pre><I>A</I>(<I>i</I>,<I>j</I>)  =  <I>A</I>(<I>i </I>- 1,<I>A</I>(i,<I>j</I> - 1))  for <I>i</I>,<I>j</I> <img src="../images/gteq.gif"> 2 .</sub></sup></pre><P>
Figure 22.6 shows the value of the function for small values of <I>i</I> and <I>j</I>.<P>
Figure 22.7 shows schematically why Ackermann's function has such explosive growth. The first row, exponential in the column number <I>j</I>, is already rapidly growing. The second row consists of the widely spaced subset of columns <img src="451_e.gif">, . . . of the first row. Lines between adjacent rows indicate columns in the lower-numbered row that are in the subset included in the higher-numbered row. The third row consists of the even more widely spaced subset of columns <img src="451_f.gif">, . . . of the second row, which is an even sparser subset of columns of the first row. In general, the spacing between columns of row <I>i</I> - 1 appearing in row <I>i</I> increases dramatically with both the column number and the row number. Observe that <img src="452_b.gif"> for all integers <I>j</I> <img src="../images/gteq.gif"> 1. Thus, for <I>i</I> &gt; 2, the function <I>A</I>(<I>i</I>, <I>j</I>) grows even more quickly than <img src="452_c.gif">.<P>
<img src="452_a.gif"><P>
<h4><a name="0897_170c">Figure 22.7 The explosive growth of Ackermann's function. Lines between rows i - 1 and i indicate entries of row i - 1 appearing in row i. Due to the explosive growth, the horizontal spacing is not to scale. The horizontal spacing between entries of row i - 1 appearing in row i greatly increases with the column number and row number. If we trace the entries in row i to their original appearance in row 1, the explosive growth is even more evident.<a name="0897_170c"></sub></sup></h4><P>
<a name="0897_170a">We define the inverse of Ackermann's function by<SUP>2<P>
<pre><img src="../images/alpha12.gif">(<I>m</I>,<I>n</I>) = <I>min</I> {<I>i</I> <img src="../images/gteq.gif"> 1: <I>A</I>(<I>i</I>, <img src="../images/hfbrdl12.gif"><I>m</I>/<I>n</I><img src="../images/hfbrdr12.gif">) &gt; lg <I>n</I>} .</sub></sup></pre><P>
<SUP>2</SUP>Although this function is not the inverse of Ackermann's function in the true mathematical sense, it captures the spirit of the inverse in its growth, which is as slow as Ackermann's function is fast. The reason we use the mysterious lg <I>n</I> threshold is revealed in the proof of the <I>O</I>(<I>m</I> <img src="../images/alpha12.gif"><I></I>(<I>m</I>, <I>n</I>)) running time, which is beyond the scope of this book.<P>
If we fix a value of <I>n</I>, then as <I>m</I> increases, the function <img src="../images/alpha12.gif">(<I>m</I>, <I>n</I>) is monotonically decreasing. To see this property, note that <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> is monotonically increasing as <I>m</I> increases; therefore, since <I>n</I> is fixed, the smallest value of <I>i </I>needed to bring <I>A</I>(<I>i</I>,<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>) above lg <I>n</I> is monotonically decreasing. This property corresponds to our intuition about disjoint-set forests with path compression: for a given number of distinct elements <I>n</I>, as the number of operations <I>m</I> increases, we would expect the average find-path length to decrease due to path compression. If we perform <I>m</I> operations in time <I>O</I>(<I>m</I> <img src="../images/alpha12.gif">(<I>m</I>, <I>n</I>)), then the average time per operation is <I>O</I>(<img src="../images/alpha12.gif">(<I>m</I>, <I>n</I>)), which is monotonically decreasing as <I>m</I> increases.<P>
To back up our earlier claim that <img src="../images/alpha12.gif">(<I>m</I>, <I>n</I>) <img src="../images/lteq12.gif"> 4 for all practical purposes, we first note that the quantity <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> is at least 1, since <I>m</I> <img src="../images/gteq.gif"> <I>n</I>. Since Ackermann's function is strictly increasing with each argument, <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> <img src="../images/gteq.gif"> 1 implies <I>A</I>(<I>i</I>, <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>) <img src="../images/gteq.gif"> <I>A</I>(<I>i</I>, 1) for all <I>i</I> <img src="../images/gteq.gif"> 1. In particular, <I>A</I>(4, <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>m</I></FONT>/<I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>) <img src="../images/gteq.gif"> <I>A</I>(4, 1). But we also have that<P>
<img src="453_a.gif"><P>
which is far greater than the estimated number of atoms in the observable universe (roughly 10<SUP>80</SUP>). It is only for impractically large values of <I>n</I> that <I>A</I>(4, 1) <img src="../images/lteq12.gif"> 1g <I>n</I>, and thus <img src="../images/alpha12.gif">(<I>m, n</I>) <img src="../images/lteq12.gif"> 4 for all practical purposes. Note that the <I>O</I>(<I>m</I> 1g<SUP>*</SUP> <I>n</I>) bound is only slightly weaker than the <I>O</I>(<I>m </I><img src="../images/alpha12.gif">(<I>m, n</I>)) bound; 1g<SUP>*</SUP>65536 = 4 and 1g<SUP>*</SUP> 2<SUP>65536</SUP> = 5, so 1g<SUP>*</SUP> <I>n</I> <img src="../images/lteq12.gif"> 5 for all practical purposes.<P>
<P>







<h2>Properties of ranks</h2><P>
<a name="0898_170b"><a name="0898_170c">In the remainder of this section, we prove an <I>O</I>(<I>m</I> 1g<SUP>*</SUP> <I>n</I>) bound on the running time of the disjoint-set operations with union by rank and path compression. In order to prove this bound, we first prove some simple properties of ranks.<P>
<a name="0898_170e">Lemma 22.2<a name="0898_170e"><P>
For all nodes <I>x</I>, we have <I>rank</I>[<I>x</I>] <img src="../images/lteq12.gif"> <I>rank</I>[<I>p</I>[<I>x</I>]], with strict inequality if <I>x</I> <img src="../images/noteq.gif"> <I>p</I>[<I>x</I>]. The value of <I>rank</I>[<I>x</I>] is initially 0 and increases through time until <I>x</I> <img src="../images/noteq.gif"> <I>p</I>[<I>x</I>]; from then on, <I>rank</I>[<I>x</I>] does not change. The value of <I>rank</I>[<I>p</I>[<I>x</I>]] is a monotonically increasing function of time.<P>
<I><B>Proof     </I></B>The proof is a straightforward induction on the number of operations, using the implementations of <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT>, <FONT FACE="Courier New" SIZE=2>UNION</FONT>, and <FONT FACE="Courier New" SIZE=2>FIND</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT> that appear in Section 22.3. We leave it as Exercise 22.4-1.      <P>
<a name="0898_170d">We define size(<I>x</I>) to be the number of nodes in the tree rooted at node <I>x</I>, including node <I>x</I> itself.<P>
<a name="0898_170f">Lemma 22.3<a name="0898_170f"><P>
For all tree roots <I>x</I>, size(<I>x</I>) <img src="../images/gteq.gif"> 2<I><SUP>rank</I>[<I>x</I>]</SUP>.<P>
<I><B>Proof     </I></B>The proof is by induction on the number of <FONT FACE="Courier New" SIZE=2>LINK</FONT> operations. Note that <FONT FACE="Courier New" SIZE=2>FIND</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT> operations change neither the rank of a tree root nor the size of its tree.<P>
<I>Basis:</I> The lemma is true before the first <FONT FACE="Courier New" SIZE=2>LINK</FONT>, since ranks are initially 0 and each tree contains at least one node.<P>
<I>Inductive step:</I> Assume that the lemma holds before performing the operation <FONT FACE="Courier New" SIZE=2>LINK</FONT>(<I>x, y</I>). Let <I>rank</I> denote the rank just before the <FONT FACE="Courier New" SIZE=2>LINK</FONT>, and let <I>rank</I>' denote the rank just after the <FONT FACE="Courier New" SIZE=2>LINK</FONT>. Define size and size' similarly.<P>
If <I>rank</I>[<I>x</I>] <img src="../images/noteq.gif"> <I>rank</I>[<I>y</I>], assume without loss of generality that <I>rank</I>[<I>x</I>] &lt; <I>rank</I>[<I>y</I>]. Node <I>y</I> is the root of the tree formed by the <FONT FACE="Courier New" SIZE=2>LINK</FONT> operation, and<P>
<pre>size'(<I>y</I>)  =  size(<I>x</I>) + size(<I>y</I>)</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  2<I><SUP>rank</I>[<I>x</I>]</SUP> + 2<I><SUP>rank</I>[<I>y</I>]</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  2<I><SUP>rank</I>[<I>y</I>]</sub></sup></pre><P>
<pre>=  2<I><SUP>rank</I></SUP>'[<I>y</I>]<SUP>.</sub></sup></pre><P>
No ranks or sizes change for any nodes other than <I>y</I>.<P>
If <I>rank</I>[<I>x</I>] = <I>rank</I>[<I>y</I>], node <I>y</I> is again the root of the new tree, and<P>
<pre>size'(<I>y</I>)  =  size(<I>x</I>) + size(<I>y</I>)</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  2<I><SUP>rank</I>[<I>x</I>]</SUP> + 2<I><SUP>rank</I>[<I>y</I>]</sub></sup></pre><P>
<pre>=  2<I><SUP>rank</I>[<I>y</I>]+ 1</sub></sup></pre><P>
<pre>=  2<I><SUP>rank</I></SUP>'[<I>y</I>]<SUP> .      </sub></sup></pre><P>
<a name="0898_1710">Lemma 22.4<a name="0898_1710"><P>
For any integer <I>r</I> <img src="../images/gteq.gif"> 0, there are at most <I>n</I>/2<I><SUP>r</I></SUP> nodes of rank <I>r</I>.<P>
<I><B>Proof     </I></B>Fix a particular value of <I>r</I>. Suppose that when we assign a rank <I>r </I>to a node <I>x</I> (in line 2 of <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT> or in line 5 of <FONT FACE="Courier New" SIZE=2>LINK</FONT>), we attach a label <I>x</I> to each node in the tree rooted at <I>x</I>. By Lemma 22.3, at least 2<I><SUP>r </I></SUP>nodes are labeled each time. Suppose that the root of the tree containing node <I>x</I> changes. Lemma 22.2 assures us that the rank of the new root (or, in fact, of any proper ancestor of <I>x</I>) is at least <I>r</I> + 1. Since we assign labels only when a root is assigned a rank <I>r</I>, no node in this new tree will ever again be labeled. Thus, each node is labeled at most once, when its root is first assigned rank <I>r</I>. Since there are <I>n</I> nodes, there are at most <I>n</I> labeled nodes, with at least 2<I><SUP>r</I></SUP> labels assigned for each node of rank <I>r</I>. If there were more than <I>n</I>/2<I><SUP>r</I></SUP> nodes of rank <I>r</I>, then more than 2<I><SUP>r</I></SUP>. (<I>n</I>/2<I><SUP>r</I></SUP>) = <I>n</I> nodes would be labeled by a node of rank <I>r</I>, which is a contradiction. Therefore, at most <I>n</I>/2<I><SUP>r</I></SUP> nodes are ever assigned rank <I>r</I>.      <P>
<a name="0898_1711">Corollary 22.5<a name="0898_1711"><P>
Every node has rank at most <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>.<P>
<I><B>Proof     </I></B>If we let <I>r</I> &gt; 1g <I>n</I>, then there are at most <I>n</I>/2<I><SUP>r</I></SUP> &lt; 1 nodes of rank <I>r</I>. Since ranks are natural numbers, the corollary follows.      <P>
<P>







<h2>Proving the time bound</h2><P>
<a name="0899_170e"><a name="0899_170f"><a name="0899_1710"><a name="0899_1711">We shall use the aggregate method of amortized analysis (see Section 18.1) to prove the <I>O</I>(<I>m</I> 1g<SUP>*</SUP> <I>n</I>) time bound. In performing the amortized analysis, it is convenient to assume that we invoke the LINK operation rather than the UNION operation. That is, since the parameters of the LINK procedure are pointers to two roots, we assume that the appropriate FIND-SET operations are performed if necessary. The following lemma shows that even if we count the extra FIND-SET operations, the asymptotic running time remains unchanged.<P>
<a name="0899_1712">Lemma 22.6<a name="0899_1712"><P>