chap02.htm

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

<a name="06f2_000a">2.1-8<a name="06f2_000a"><P>
We can extend our notation to the case of two parameters <I>n</I> and <I>m</I> that can go to infinity independently at different rates. For a given function <I>g</I>(<I>n</I>,<I> m</I>), we denote by <I>O</I>(<I>g</I>(<I>n, m</I>)) the set of functions<P>
<I>O</I>(<I>g</I>(<I>n</I>, <I>m</I>)) = {<img src="../images/scrptf12.gif">(<I>n,m</I>): there exist positive constants <I>c</I>, <I>n</I><SUB>0</SUB>, and <I>m</I><SUB>0<P>
such that 0 <img src="../images/lteq12.gif"> <img src="../images/scrptf12.gif"> (<I>n, m</I>) <img src="../images/lteq12.gif"> <I>cg</I>(<I>n, m</I>)<P>
for all <I>n</I> <img src="../images/gteq.gif"><I>n</I><SUB>0</SUB> and <I>m</I> <img src="../images/gteq.gif"> <I>m</I><SUB>0</SUB>}.<P>
Give corresponding definitions for <img src="../images/omega12.gif">(<I>g</I>(<I>n</I>, <I>m</I>)) and <img src="../images/bound.gif">(<I>g</I>(<I>n</I>, <I>m</I>)).<P>
<P>


<P>







<h1><a name="06f3_0001">2.2 Standard notations and common functions<a name="06f3_0001"></h1><P>
This section reviews some standard mathematical functions and notations and explores the relationships among them. It also illustrates the use of the asymptotic notations.<P>





<h2>Monotonicity</h2><P>
<a name="06f4_118c"><a name="06f4_118d"><a name="06f4_118e"><a name="06f4_118f">A function <img src="../images/scrptf12.gif"> (<I>n</I>) is <I><B>monotonically increasing</I></B> if <I>m</I> <img src="../images/lteq12.gif"> <I>n</I> implies <img src="../images/scrptf12.gif"> (<I>m</I>) <img src="../images/lteq12.gif"> <img src="../images/scrptf12.gif"> (<I>n</I>). Similarly, it is <I><B>monotonically decreasing</I></B> if <I>m</I> <img src="../images/lteq12.gif"> <I>n</I> implies <img src="../images/scrptf12.gif"> (<I>m</I>) <img src="../images/gteq.gif"> <img src="../images/scrptf12.gif"> (<I>n</I>). A function <img src="../images/scrptf12.gif">(<I>n</I>) is <B>strictly increasing</B> if <I>m</I> &lt; <I>n</I> implies <img src="../images/scrptf12.gif">(<I>m</I>) &lt; <img src="../images/scrptf12.gif">(<I>n</I>) and <I><B>strictly decreasing</I></B> if <I>m</I> &lt; <I>n</I> implies <img src="../images/scrptf12.gif"> (<I>m</I>) &gt; <img src="../images/scrptf12.gif"> (<I>n</I>).<P>
<P>







<h2>Floors and ceilings</h2><P>
<a name="06f5_1190"><a name="06f5_1191"><a name="06f5_1192"><a name="06f5_1193">For any real number <I>x</I>, we denote the greatest integer less than or equal to <I>x</I> by <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>x</I><img src="../images/hfbrdr12.gif"></FONT> (read &quot;the floor of <I>x</I>&quot;) and the least integer greater than or equal to x by <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"><I>x</I><img src="../images/hfbrur14.gif"></FONT> (read &quot;the ceiling of <I>x</I>&quot;). For all real <I>x</I>,<P>
<pre><I>x</I> - 1 &lt; <img src="../images/hfbrdl12.gif"><I>x</I><img src="../images/hfbrdr12.gif"> <img src="../images/lteq12.gif"> <I>x</I> <img src="../images/lteq12.gif"> <img src="../images/hfbrul14.gif"><I>x</I><img src="../images/hfbrur14.gif"> &lt; <I>x</I> +1.</sub></sup></pre><P>
For any integer <I>n</I>,<P>
<pre><img src="../images/hfbrul14.gif"><I>n</I>/2<img src="../images/hfbrur14.gif"> + <img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdl12.gif">= <I>n,</I></sub></sup></pre><P>
and for any integer <I>n</I> and integers <I>a</I> <img src="../images/noteq.gif"> 0 and <I>b</I> <img src="../images/noteq.gif"> 0,<P>
<pre><img src="../images/hfbrul14.gif"><img src="../images/hfbrul14.gif"><I>n</I>/<I>a</I><img src="../images/hfbrur14.gif">/<I>b</I><img src="../images/hfbrur14.gif"> = <img src="../images/hfbrul14.gif"><I>n</I>/<I>ab</I><img src="../images/hfbrur14.gif"></sub></sup></pre><P>
<h4><a name="06f5_1194">(2.3)<a name="06f5_1194"></sub></sup></h4><P>
and<P>
<pre><img src="../images/hfbrdl12.gif"><img src="../images/hfbrdl12.gif"><I>n</I>/<I>a</I><img src="../images/hfbrdr12.gif">/<I>b</I><img src="../images/hfbrdr12.gif"> = <img src="../images/hfbrdl12.gif"><I>n</I>/<I>ab</I><img src="../images/hfbrdr12.gif"> .</sub></sup></pre><P>
<h4><a name="06f5_1195">(2.4)<a name="06f5_1195"></sub></sup></h4><P>
The floor and ceiling functions are monotonically increasing.<P>
<P>







<h2>Polynomials</h2><P>
<a name="06f6_1194"><a name="06f6_1195"><a name="06f6_1196"><a name="06f6_1197"><a name="06f6_1198">Given a positive integer <I>d</I>, a <I><B>polynomial in n of degree</I></B> <I>d</I> is a function <I>p</I>(<I>n</I>) of the form<P>
<img src="33_a.gif"><P>
where the constants <I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . ., <I>a<SUB>d</I></SUB> are the <I><B>coefficients </I></B>of the polynomial and <I>a<SUB>d</I></SUB> <img src="../images/noteq.gif"> 0. A polynomial is <I><B>asymptotically positive</I></B> if and only if <I>a<SUB>d</SUB> </I>&gt; 0. For an asymptotically positive polynomial <I>p</I>(<I>n</I>) of degree <I>d</I>, we have <I>p</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n<SUP>d</I></SUP>). For any real constant <I>a</I> <img src="../images/gteq.gif"> 0, the function <I>n<SUP>a</I></SUP> is monotonically increasing, and for any real constant <I>a</I> <img src="../images/lteq12.gif"> 0, the function <I>n<SUP>a</I></SUP> is monotonically decreasing. We say that a function <img src="../images/scrptf12.gif">(<I>n</I>) is <I><B>polynomially bounded</I></B> if <img src="../images/scrptf12.gif">(<I>n</I>) = <I>n<SUP>0</I>(1)</SUP>, which is equivalent to saying that <img src="../images/scrptf12.gif">(<I>n</I>) = <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I> (see Exercise 2.2-2).<P>
<P>







<h2>Exponentials</h2><P>
<a name="06f7_1199">For all real <I>a</I> <img src="../images/noteq.gif"> 0, <I>m</I>, and <I>n</I>, we have the following identities:<P>
<pre><I>a</I><SUP>0</SUP>  =  1,</sub></sup></pre><P>
<pre><I>a</I><SUP>1</SUP>  =  <I>a</I>,</sub></sup></pre><P>
<pre><I>a<SUP></I></SUP>-<SUP>1</SUP>  =   1/<I>a</I>,</sub></sup></pre><P>
<pre>(<I>a<SUP>m</I></SUP>)<I><SUP>n</I></SUP>  =   <I>a<SUP>mn</I></SUP>,</sub></sup></pre><P>
<pre>(<I>a<SUP>m</I></SUP>)<I><SUP>n</I></SUP>  =   (<I>a<SUP>n</I></SUP>)<I><SUP>m</I></SUP>,</sub></sup></pre><P>
<pre>a<I><SUP>m</I></SUP>a<I><SUP>n</I></SUP>   =   a<I><SUP>m</I>+<I>n</I></SUP>.</sub></sup></pre><P>
For all <I>n</I> and <I>a</I> <img src="../images/gteq.gif"> 1, the function <I>a<SUP>n</I></SUP> is monotonically increasing in <I>n</I>. When convenient, we shall assume 0<SUP>0</SUP> = 1.<P>
The rates of growth of polynomials and exponentials can be related by the following fact. For all real constants <I>a</I> and <I>b</I> such that <I>a</I> &gt; 1,<P>
<img src="33_b.gif"><P>
<h4><a name="06f7_119a">(2.5)<a name="06f7_119a"></sub></sup></h4><P>
from which we can conclude that<P>
<pre><I>n<SUP>b</I></SUP> = <I>0</I>(<I>a<SUP>n</I></SUP>).</sub></sup></pre><P>
Thus, any positive exponential function grows faster than any polynomial.<P>
Using <I>e </I>to denote 2.71828 . . ., the base of the natural logarithm function, we have for all real <I>x</I>,<P>
<img src="34_a.gif"><P>
<h4><a name="06f7_119b">(2.6)<a name="06f7_119b"></sub></sup></h4><P>
where &quot;!&quot; denotes the factorial function defined later in this section. For all real <I>x</I>, we have the inequality<P>
<pre><I>e<SUP>x </I></SUP><img src="../images/gteq.gif"> 1 + <I>x</I>,</sub></sup></pre><P>
<h4><a name="06f7_119c">(2.7)<a name="06f7_119c"></sub></sup></h4><P>
where equality holds only when x = 0. When <FONT FACE="Times New Roman" SIZE=2>|<I>x</I>|</FONT> <img src="../images/lteq12.gif"> 1, we have the approximation<P>
<pre>1 + <I>x</I> <img src="../images/lteq12.gif"> <I>e<SUP>x</I></SUP> <img src="../images/lteq12.gif"> l + <I>x</I> +<I>x</I><SUP>2 .</sub></sup></pre><P>
<h4><a name="06f7_119d">(2.8)<a name="06f7_119d"></sub></sup></h4><P>
When <I>x</I> <img src="../images/arrow12.gif"> 0, the approximation of <I>e<SUP>x</I></SUP> by 1 + <I>x</I> is quite good:<P>
<pre><I>e<SUP>x</I></SUP> = 1 + <I>x</I> + <img src="../images/bound.gif">(<I>x</I><SUP>2</SUP>).</sub></sup></pre><P>
(In this equation, the asymptotic notation is used to describe the limiting behavior as <I>x</I> <img src="../images/arrow12.gif"> 0 rather than as <I>x</I> <img src="../images/arrow12.gif"> <img src="../images/infin.gif">.) We have for all <I>x,</I><P>
<img src="34_b.gif"><P>
<P>