chap02.htm

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

<h2>Logarithms</h2><P>
<a name="06f8_119a"><a name="06f8_119b"><a name="06f8_119c"><a name="06f8_119d"><a name="06f8_119e">We shall use the following notations:<P>
<pre>lg <I>n</I>   =   log<SUB>2</SUB> <I>n</I>     (binary logarithm),</sub></sup></pre><P>
<pre>l<I>n</I> <I>n</I>   =   log<I><SUB>e</I></SUB> <I>n</I>     (natural logarithm),</sub></sup></pre><P>
<pre>lg<I><SUP>k</I></SUP> <I>n</I>   =   (lg <I>n</I>)<I><SUP>k</I></SUP>    (exponentiation),</sub></sup></pre><P>
<pre>lg lg <I>n</I>  =  lg(lg <I>n</I>)    (composition).</sub></sup></pre><P>
An important notational convention we shall adopt is that <I>logarithm functions will apply only to the next term in the formula</I>, so that lg<I> n</I> + <I>k</I> will mean (lg <I>n</I>) + <I>k</I> and not lg(<I>n</I> + <I>k</I>). For <I>n</I> &gt; 0 and <I>b</I> &gt; 1, the function log<I><SUB>b</I></SUB> <I>n</I> is strictly increasing.<P>
For all real <I>a</I> &gt; 0, <I>b</I> &gt; 0, <I>c</I> &gt; 0, and <I>n</I>,<P>
<img src="34_c.gif"><P>
<h4><a name="06f8_11a1">(2.9)<a name="06f8_11a1"></sub></sup></h4><P>
Since changing the base of a logarithm from one constant to another only changes the value of the logarithm by a constant factor, we shall often use the notation &quot;lg <I>n</I>&quot; when we don't care about constant factors, such as in <I>O</I>-notation. Computer scientists find 2 to be the most natural base for logarithms because so many algorithms and data structures involve splitting a problem into two parts.<P>
There is a simple series expansion for ln(1 + <I>x</I>) when <img src="../images/sglvrt.gif"><I>x</I><img src="../images/sglvrt.gif"> &lt; 1:<P>
<img src="35_a.gif"><P>
We also have the following inequalities for <I>x</I> &gt; -1:<P>
<img src="35_b.gif"><P>
<h4><a name="06f8_11a2">(2.10)<a name="06f8_11a2"></sub></sup></h4><P>
where equality holds only for <I>x</I> = 0.<P>
<a name="06f8_119f"><a name="06f8_11a0">We say that a function <I>f</I>(<I>n</I>) is <I><B>polylogarithmically bounded</I> </B>if <I>f</I>(<I>n</I>) = lg<I>O</I><SUP>(1)</SUP> <I>n</I>. We can relate the growth of polynomials and polylogarithms by substituting lg <I>n</I> for <I>n</I> and 2<I><SUP>a</I></SUP> for <I>a</I> in equation (2.5), yielding <P>
<img src="35_c.gif"><P>
From this limit, we can conclude that<P>
<pre>lg<I><SUP>b</I></SUP> <I>n</I> = <I>o</I>(<I>n<SUP>a</I></SUP>)</sub></sup></pre><P>
for any constant <I>a</I> &gt; 0. Thus, any positive polynomial function grows faster than any polylogarithmic function.<P>
<P>







<h2>Factorials</h2><P>
<a name="06f9_11a1"><a name="06f9_11a2">The notation <I>n</I>! (read "<I>n</I> factorial") is defined for integers <I>n</I> <img src="../images/gteq.gif"> 0 as<P>
<img src="35_d.gif"><P>
Thus, <I>n</I>! = 1.2.3...<I>n</I>.<P>
<a name="06f9_11a3">A weak upper bound on the factorial function is <I>n</I>! <img src="../images/lteq12.gif"> <I>n<SUP>n</I></SUP>, since each of the <I>n</I> terms in the factorial product is at most <I>n</I>. <I><B>Stirling's approximation</I></B><I>,</I><P>
<img src="35_e.gif"><P>
<h4><a name="06f9_11a4">(2.11)<a name="06f9_11a4"></sub></sup></h4><P>
where <I>e</I> is the base of the natural logarithm, gives us a tighter upper bound, and a lower bound as well. Using Stirling's approximation, one can prove <P>
<pre><I>n</I>!  =  <I>o</I>(<I>n<SUP>n</I></SUP>),</sub></sup></pre><P>
<pre><I>n</I>!  =  <img src="../images/omega12.gif">(2<I><SUP>n</I></SUP>),</sub></sup></pre><P>
<pre>lg(<I>n</I>!)  =  <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>).</sub></sup></pre><P>
The following bounds also hold for all <I>n</I>:<P>
<img src="35_f.gif"><P>
<h4><a name="06f9_11a5">(2.12)<a name="06f9_11a5"></sub></sup></h4><P>
<P>







<h2>The iterated logarithm function</h2><P>
<a name="06fa_11a4"><a name="06fa_11a5"><a name="06fa_11a6">We use the notation lg* <I>n</I> (read &quot;log star of <I>n</I>&quot;) to denote the iterated logarithm, which is defined as follows. Let the function lg<SUP>(<I>i</I>)</SUP> <I>n</I> be defined recursively for nonnegative integers <I>i</I> as<P>
<img src="36_a.gif"><P>
Be sure to distinguish lg<SUP>(<I>i</I>)</SUP> <I>n</I> (the logarithm function applied <I>i</I> times in succession, starting with argument <I>n</I>) from lg<I><SUP>i</I></SUP> <I>n</I> (the logarithm of <I>n</I> raised to the <I>i</I>th power). The iterated logarithm function is defined as<P>
<img src="36_b.gif"><P>
The iterated logarithm is a <I>very</I> slowly growing function:<P>
<pre>lg* 2  =  1,</sub></sup></pre><P>
<pre>lg* 4  =  2,</sub></sup></pre><P>
<pre>lg* 16   =  3,</sub></sup></pre><P>
<pre>lg* 65536     =  4,</sub></sup></pre><P>
<pre>lg*(2<SUP>65536</SUP>)     =  5.</sub></sup></pre><P>
Since the number of atoms in the observable universe is estimated to be about 10<SUP>80</SUP>, which is much less than 2<SUP>65536</SUP>, we rarely encounter a value of <I>n</I> such that lg* <I>n</I> &gt; 5.<P>
<P>







<h2>Fibonacci numbers</h2><P>
<a name="06fb_11a7">The <I><B>Fibonacci numbers</I></B> are defined by the following recurrence:<P>
<pre><I>F</I><SUB>0</SUB>  =  0,</sub></sup></pre><P>
<pre><I>F</I><SUB>1</SUB>  =  1,</sub></sup></pre><P>
<pre><I>F<SUB>i</I></SUB>  =  <I>F<SUB>i</I>-1</SUB>+<I>F<SUB>i</I>-2</SUB>  for <I>i</I> <img src="../images/gteq.gif"> 2.</sub></sup></pre><P>
<h4><a name="06fb_11a9">(2.13)<a name="06fb_11a9"></sub></sup></h4><P>
Thus, each Fibonacci number is the sum of the two previous ones, yielding the sequence<P>
<pre>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .</sub></sup></pre><P>
<a name="06fb_11a8">Fibonacci numbers are related to the <I><B>golden ratio</I></B> <img src="../images/phicap12.gif"><I></I> and to its conjugate <img src="36_c.gif">, which are given by the following formulas:<P>
<img src="36_d.gif"><P>
<h4><a name="06fb_11aa">(2.14)<a name="06fb_11aa"></sub></sup></h4><P>
Specifically, we have<P>
<img src="37_a.gif"><P>
<h4><a name="06fb_11ab">(2.15)<a name="06fb_11ab"></sub></sup></h4><P>
which can be proved by induction (Exercise 2.2-7). Since <img src="37_b.gif"> &lt; 1, we have <img src="37_c.gif">, so that the <I>i</I>th Fibonacci number <I>F<SUB>i</I></SUB> is equal to <img src="37_d.gif"> rounded to the nearest integer. Thus, Fibonacci numbers grow exponentially.<P>
<P>







<h2><a name="06fc_0001">Exercises<a name="06fc_0001"></h2><P>