chap02.htm

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

<pre>2<I>n</I><SUP>2</SUP> + <img src="../images/bound.gif">(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>).</sub></sup></pre><P>
We interpret such equations using the following rule: <I>No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid</I>. Thus, the meaning of our example is that for any function <img src="../images/scrptf12.gif">(<I>n</I>) <img src="../images/memof12.gif"> <img src="../images/bound.gif">(<I>n</I>), there is some function g(n) <img src="../images/memof12.gif"> <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) such that 2<I>n</I><SUP>2</SUP> + <img src="../images/scrptf12.gif">(<I>n</I>) = <I>g</I>(<I>n</I>) for all <I>n</I>. In other words, the right-hand side of an equation provides coarser level of detail than the left-hand side.<P>
A number of such relationships can be chained together, as in<P>
<pre>2<I>n</I><SUP>2</SUP> + 3<I>n</I> + 1 = 2<I>n</I><SUP>2</SUP> + <img src="../images/bound.gif">(<I>n</I>)</sub></sup></pre><P>
<pre>= <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>).</sub></sup></pre><P>
We can interpret each equation separately by the rule above. The first equation says that there is <I>some</I> function <img src="../images/scrptf12.gif"><I>(</I>n<I>) <img src="../images/memof12.gif"> <img src="../images/bound.gif"></I>(<I>n</I>) such that 2<I>n</I><SUP>2</SUP> + 3<I>n</I> + 1 = 2<I>n</I><SUP>2</SUP> + <img src="../images/scrptf12.gif"><I>(</I>n<I>) for all </I>n.<I> The second equation says that for </I>any<I> function </I>g<I>(</I>n<I>)</I> <I><img src="../images/memof12.gif"> </I><img src="../images/bound.gif"><I>(</I>n<I>) (such as the <img src="../images/scrptf12.gif"></I>(<I>n</I>) just mentioned), there is <I>some</I> function <I>h</I>(<I>n</I>)<I> </I><img src="../images/memof12.gif"> <I><img src="../images/bound.gif"></I>(<I>n</I><SUP>2</SUP>) such that 2<I>n</I><SUP>2</SUP><I> + g</I>(<I>n</I>)<I> = h</I>(<I>n</I>) for all <I>n.</I> Note that this interpretation implies that 2<I>n</I><SUP>2</SUP> + 3<I>n</I> + 1 = <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>), which is what the chaining of equations intuitively gives us.<P>
<P>







<h2>o-notation</h2><P>
<a name="06ef_1185">The asymptotic upper bound provided by <I>O</I>-notation may or may not be asymptotically tight. The bound 2<I>n</I><SUP>2</SUP><I> = O</I>(<I>n</I><SUP>2</SUP>) is asymptotically tight, but the bound 2<I>n = O</I>(<I>n</I><SUP>2</SUP>) is not. We use <I>o</I>-notation to denote an upper bound that is not asymptotically tight. We formally define <I>o</I>(<I>g</I>(<I>n</I>)) ("little-oh of <I>g</I> of <I>n</I>") as the set<P>
<I>o</I>(<I>g</I>(<I>n</I>)) = {<img src="../images/scrptf12.gif"><I></I>(<I>n</I>): for any positive constant <I>c &gt; </I>0<I>, </I>there exists a constant<P>
<I>n</I><SUB>0</SUB> &gt; 0 such that 0 <img src="../images/lteq12.gif"> <I>f</I>(<I>n</I>) &lt; <I>cg</I>(<I>n</I>) for all <I>n</I> <img src="../images/gteq.gif"> <I>n</I><SUB>0</SUB>}.<P>
For example, 2n = o(n<SUP>2</SUP>), but 2n<SUP>2</SUP> <img src="../images/noteq.gif"> o(n<SUP>2</SUP>).<P>
The definitions of <I>O</I>-notation and <I>o</I>-notation are similar. The main difference is that in <img src="../images/scrptf12.gif"><I>(</I>n<I>)</I> = O<I>(</I>g<I>(</I>n<I>)), the bound 0 <img src="../images/lteq12.gif"> <img src="../images/scrptf12.gif"></I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cg</I>(<I>n</I>) holds for <I>some</I> constant <I>c</I> &gt; 0, but in <img src="../images/scrptf12.gif"><I>(</I>n<I>)</I> = o<I>(</I>g<I>(</I>n<I>)), the bound 0 <img src="../images/lteq12.gif"> <img src="../images/scrptf12.gif"></I>(<I>n</I>)<I> &lt; cg</I>(<I>n</I>) holds for all constants <I>c</I> &gt; 0. Intuitively, in the <I>o</I>-notation, the function <I>f</I>(<I>n</I>) becomes insignificant relative to <I>g</I>(<I>n</I>) as <I>n</I> approaches infinity; that is,<P>
<img src="30_a.gif"><P>
<h4><a name="06ef_1186">(2.1)<a name="06ef_1186"></sub></sup></h4><P>
Some authors use this limit as a definition of the <I>o</I>-notation; the definition in this book also restricts the anonymous functions to be asymptotically nonnegative.<P>
<P>







<h2><img src="../images/omega12.gif">-notation</h2><P>
<a name="06f0_1186">By analogy, <img src="../images/omega12.gif">-notation is to <img src="../images/omega12.gif">-notation as <I>o</I>-notation is to <I>O</I>-notation. We use <img src="../images/omega12.gif">-notation to denote a lower bound that is not asymptotically tight. One way to define it is by<P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) <img src="../images/memof12.gif"> <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)) if and only if <I>g</I>(<I>n</I>) <img src="../images/memof12.gif"> <I>o</I>(<img src="../images/scrptf12.gif">(<I>n</I>)).</sub></sup></pre><P>
Formally, however, we define <img src="../images/omega12.gif"> (<I>g</I>(<I>n</I>)) (&quot;little-omega of <I>g</I> of <I>n</I>&quot;) as the set<P>
<img src="../images/omega12.gif"><I>(</I>g<I>(</I>n<I>)) = {<img src="../images/scrptf12.gif"></I>(<I>n</I>): for any positive constant <I>c</I> &gt; 0, there exists a constant<P>
<I>n</I><SUB>0</SUB> &gt; 0 such that 0 <img src="../images/lteq12.gif"> <I>cg</I>(<I>n</I>) &lt; <img src="../images/scrptf12.gif">(<I>n</I>) for all <I>n</I> <img src="../images/gteq.gif"> <I>n</I><SUB>0</SUB>}.<P>
For example, <I>n<SUP>2</I></SUP>/2 = <img src="../images/omega12.gif"><I>(</I>n<I>), but </I>n<I><SUP>2</SUP></I>/2 <I><img src="../images/noteq.gif"></I> <I><img src="../images/omega12.gif">(</I>n<SUP>2<I></SUP>). The relation <img src="../images/scrptf12.gif">(</I>n<I>) = <img src="../images/omega12.gif">(</I>g<I>(</I>n<I>)) implies that</I><P>
<img src="30_b.gif"><P>
if the limit exists. That is, <img src="../images/scrptf12.gif"><I></I>(<I>n</I>) becomes arbitrarily large relative to <I>g</I>(<I>n</I>) as <I>n</I> approaches infinity.<P>
<P>







<h2>Comparison of functions</h2><P>
<a name="06f1_1187"><a name="06f1_1188"><a name="06f1_1189"><a name="06f1_118a">Many of the relational properties of real numbers apply to asymptotic comparisons as well. For the following, assume that <img src="../images/scrptf12.gif">(<I>n</I>) and <I>g</I>(<I>n</I>) are asymptotically positive.<P>
Transitivity:<P>
<pre><I>&acirc;</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>h</I>(<I>n</I>)) imply &acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>h</I>(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <I>O</I>(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>) = <I>O</I>(<I>h</I>(<I>n</I>)) imply &acirc;(<I>n</I>) = <I>O</I>(<I>h</I>(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>h</I>(<I>n</I>)) imply &acirc;(<I>n</I>) = <img src="../images/omega12.gif">(<I>h</I>(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <I>o</I>(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>) = <I>o</I>(<I>h</I>(<I>n</I>)) imply &acirc;(<I>n</I>) = <I>o</I>(<I>h</I>(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>h</I>(<I>n</I>)) imply &acirc;(<I>n</I>) = <img src="../images/omega12.gif">(<I>h</I>(<I>n</I>)).</sub></sup></pre><P>
Reflexivity:<P>
<pre><I>&acirc;</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <I>O</I>(&acirc;(<I>n</I>)),</sub></sup></pre><P>
<pre><I>&acirc;</I>(<I>n</I>) = <img src="../images/omega12.gif">(&acirc;(<I>n</I>)),</sub></sup></pre><P>
Symmetry:<P>
<pre>&acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>g</I>(<I>n</I>)) if and only if <I>g</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)).</sub></sup></pre><P>
Transpose symmetry:<P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) =<I> O</I>(<I>g</I>(<I>n</I>)) if and only if <I>g</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>f</I>(<I>n</I>)),</sub></sup></pre><P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <I>o</I>(<I>g</I>(<I>n</I>)) if and only if <I>g</I>(<I>n</I>) = <img src="../images/omega12.gif">(<img src="../images/scrptf12.gif"><I>(</I>n<I>)).</I></sub></sup></pre><P>
Because these properties hold for asymptotic notations, one can draw an analogy between the asymptotic comparison of two functions <I>f</I> and <I>g</I> and the comparison of two real numbers <I>a</I> and <I>b</I>:<P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <I>O</I>(<I>g</I>(<I>n</I>))  <img src="../images/approx18.gif">  <I>a</I> <img src="../images/lteq12.gif"> <I>b</I>,</sub></sup></pre><P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>))  <img src="../images/approx18.gif">  <I>a</I> <img src="../images/gteq.gif"> <I>b</I>,</sub></sup></pre><P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <img src="../images/bound.gif">(<I>g</I>(<I>n</I>))  <img src="../images/approx18.gif">  <I>a</I> = <I>b</I>,</sub></sup></pre><P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <I>o</I>(<I>g</I>(<I>n</I>))  <img src="../images/approx18.gif">  <I>a</I> &lt; <I>b</I>,</sub></sup></pre><P>
<pre><img src="../images/scrptf12.gif">(<I>n</I>) = <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>))  <img src="../images/approx18.gif">  <I>a</I> &gt; <I>b</I>.</sub></sup></pre><P>
<a name="06f1_118b">One property of real numbers, however, does not carry over to asymptotic notation:<P>
<B>Trichotomy:     </B>For any two real numbers <I>a</I> and <I>b</I>, exactly one of the following must hold: <I>a</I> &lt; <I>b</I>, <I>a</I> = <I>b</I>, or <I>a</I> &gt; <I>b</I>.<P>
Although any two real numbers can be compared, not all functions are asymptotically comparable. That is, for two functions <img src="../images/scrptf12.gif">(<I>n</I>) and <I>g</I>(<I>n</I>), it may be the case that neither <img src="../images/scrptf12.gif"> (<I>n</I>) = <I>O</I>(<I>g</I>(<I>n</I>)) nor <img src="../images/scrptf12.gif"> (<I>n</I>) = <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)) holds. For example, the functions <I>n</I> and <I>n</I> <SUP>1+sin <I>n</I></SUP> cannot be compared using asymptotic notation, since the value of the exponent in <I>n</I><SUP>1 +sin <I>n</I></SUP> oscillates between 0 and 2, taking on all values in between.<P>
<P>







<h2><a name="06f2_0001">Exercises<a name="06f2_0001"></h2><P>
<a name="06f2_0002">2.1-1<a name="06f2_0002"><P>
Let <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) be asymptotically nonnegative functions. Using the basic definition of <img src="../images/bound.gif">-notation, prove that max(<img src="../images/scrptf12.gif">(<I>n</I>),<I>g</I>(<I>n</I>)) = <img src="../images/bound.gif">(<I>f</I>(<I>n</I>) + <I>g</I>(<I>n</I>)).<P>
<a name="06f2_0003">2.1-2<a name="06f2_0003"><P>
Show that for any real constants <I>a</I> and <I>b</I>, where <I>b</I> &gt; 0,<P>
<pre>(<I>n</I> + <I>a</I>)<I><SUP>b</I></SUP> = <img src="../images/bound.gif">(<I>n<SUP>b</I></SUP>) .</sub></sup></pre><P>
<h4><a name="06f2_0004">(2.2)<a name="06f2_0004"></sub></sup></h4><P>
<a name="06f2_0005">2.1-3<a name="06f2_0005"><P>
Explain why the statement, &quot;The running time of algorithm <I>A</I> is at least <I>O</I>(<I>n</I><SUP>2</SUP>),&quot; is content-free.<P>
<a name="06f2_0006">2.1-4<a name="06f2_0006"><P>
Is 2<I><SUP>n</I>+1</SUP> = <I>O</I>(2<I><SUP>n</I></SUP>)? Is 2<SUP>2<I>n</I></SUP> = <I>O</I>(2<I><SUP>n</I></SUP>)?<P>
<a name="06f2_0007">2.1-5<a name="06f2_0007"><P>
Prove Theorem 2.1.<P>
<a name="06f2_0008">2.1-6<a name="06f2_0008"><P>
Prove that the running time of an algorithm is <img src="../images/bound.gif">(<I>g</I>(<I>n</I>)) if and only if its worst-case running time is <I>O</I>(<I>g</I>(<I>n</I>)) and its best-case running time is <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)).<P>
<a name="06f2_0009">2.1-7<a name="06f2_0009"><P>
Prove that <I>o</I>(<I>g</I>(<I>n</I>)) <img src="../images/dome.gif"> <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>)) is the empty set.<P>