chap02.htm

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

<a name="06fc_0002">2.2-1<a name="06fc_0002"><P>
Show that if <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) are monotonically increasing functions, then so are the functions <I>f</I>(<I>n</I>) + <I>g</I>(<I>n</I>) and <I>f</I>(<I>g</I>(<I>n</I>)), and if <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) are in addition nonnegative, then <I>f</I>(<I>n</I>) . <I>g</I>(<I>n</I>)is monotonically increasing.<P>
<a name="06fc_0003">2.2-2<a name="06fc_0003"><P>
Use the definition of <I>O</I>-notation to show that <I>T</I>(<I>n</I>) = <I>n<SUP>o</I>(1)</SUP> if and only if there exists a constant <I>k</I> &gt; 0 such that <I>T</I>(<I>n</I>) = <I>O</I>(<I>n<SUP>k</I></SUP>).<P>
<a name="06fc_0004">2.2-3<a name="06fc_0004"><P>
Prove equation (2.9).<P>
<a name="06fc_0005">2.2-4<a name="06fc_0005"><P>
Prove that lg(<I>n</I>!) = <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) and that <I>n</I>! = <I>o</I>(<I>n<SUP>n</I></SUP>).<P>
<a name="06fc_0006">2.2-5<a name="06fc_0006"><P>
Is the function [lg <I>n</I>]! polynomially bounded? Is the function [lg lg <I>n</I>]! polynomially bounded?<P>
2.2-6     *<P>
Which is asymptotically larger: lg(lg* <I>n</I>) or lg*(lg <I>n</I>)?<P>
<a name="06fc_0007">2.2-7<a name="06fc_0007"><P>
Prove by induction that the <I>i</I>th Fibonacci number satisfies the equality <img src="37_e.gif"> where <img src="../images/phicap12.gif"><I> </I>is the golden ratio and <img src="37_f.gif"> is its conjugate.<P>
<a name="06fc_0008">2.2-8<a name="06fc_0008"><P>
Prove that for <I>i</I> <img src="../images/gteq.gif"> 0, the (<I>i</I> + 2)nd Fibonacci number satisfies <I>F<SUB>i</I>+2</SUB> <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>i<I></SUP>.</I><P>
<P>


<P>







<h1><a name="06fd_11b0">Problems<a name="06fd_11b0"></h1><P>
<a name="06fd_11b1">2-1 Asymptotic behavior of polynomials<a name="06fd_11b1"><P>
<a name="06fd_11a9">Let<P>
<img src="38_a.gif"><P>
where <I>a<SUB>d</I></SUB> &gt; 0, be a degree-<I>d</I> polynomial in <I>n</I>, and let <I>k</I> be a constant. Use the definitions of the asymptotic notations to prove the following properties.<P>
<I><B>a</I>.</B>     If <I>k</I> <img src="../images/gteq.gif"> <I>d</I>, then <I>p</I>(<I>n</I>) = <I><B>O</I></B>(<I>n<SUP>k</I></SUP>).<P>
<I><B>b</I>.</B>     If <I>k</I> <img src="../images/lteq12.gif"> <I>d</I>, then <I>p</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>n<SUP>k</I></SUP>).<P>
<I><B>c</I>.</B>     If <I>k</I> = <I>d</I>, then <I>p</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n<SUP>k</I></SUP>).<P>
<I><B>d</I>.</B>     If <I>k</I> &gt; <I>d</I>, then <I>p</I>(<I>n</I>) = <I>o</I>(<I>n<SUP>k</I></SUP>).<P>
<I><B>e</I>.</B>     If <I>k</I> &lt; <I>d</I>, then <I>p</I>(<I>n</I>) = <img src="../images/omega12.gif"><I>(</I>n<SUP>k<I></SUP>).</I><P>
<a name="06fd_11b2">2-2     Relative asymptotic growths<a name="06fd_11b2"><P>
Indicate, for each pair of expressions (<I>A, B</I>) in the table below, whether <I>A</I> is <I>O</I>, <I>o</I>, <img src="../images/omega12.gif">, <img src="../images/omega12.gif"><B>,</B> or <img src="../images/bound.gif"><B> </B>of <I>B</I>. Assume that <I>k</I> <img src="../images/gteq.gif"> 1, <img src="../images/memof12.gif"> &gt; 0, and <I>c</I> &gt; 1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.<P>
<img src="38_b.gif"><P>
<a name="06fd_11b3">2-3     Ordering by asymptotic growth rates<a name="06fd_11b3"><P>
<I><B>a.</I></B>     Rank the following functions by order of growth; that is, find an arrangement <I>g</I><SUB>1</SUB>, <I>g</I><SUB>2</SUB>, . . . ,<I>g</I><SUB>30</SUB> of the functions satisfying <I>g</I><SUB>1</SUB> = <img src="../images/omega12.gif">(g2)<SUB>, <I>g</I>2</SUB> = <img src="../images/omega12.gif">(<I>g</I><SUB>3</SUB>), ..., <I>g</I><SUB>29</SUB> = <img src="../images/omega12.gif">(<I>g</I><SUB>30</SUB>). Partition your list into equivalence classes such that <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) are in the same class if and only if <I>f</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>g</I>(<I>n</I>)).<P>
<img src="39_a.gif"><P>
<I><B>b.</I></B>     Give an example of a single nonnegative function <I>f</I>(<I>n</I>) such that for all functions <I>g<SUB>i</I></SUB>(<I>n</I>) in part (a), <I>f</I>(<I>n</I>)is neither <I>O</I>(<I>g<SUB>i</I></SUB>(<I>n</I>)) nor <img src="../images/omega12.gif">(<I>g<SUB>i</I></SUB>(<I>n</I>)).<P>
<a name="06fd_11b4">2-4     Asymptotic notation properties<a name="06fd_11b4"><P>
Let <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) be asymptotically positive functions. Prove or disprove each of the following conjectures.<P>
<I><B>a.</I></B><I>     f</I>(<I>n</I>)<I> = O</I>(<I>g</I>(<I>n</I>)) implies <I>g</I>(<I>n</I>)<I> = O</I>(<I>f</I>(<I>n</I>)).<P>
<I><B>b.</I></B>     <I>f</I>(<I>n</I>)<I> + g</I>(<I>n</I>) = <img src="../images/bound.gif">(min(&acirc;(<I>n</I>), <I>g</I>(<I>n</I>))).<P>
<I><B>c.</I></B><I>     f</I>(<I>n</I>)<I> = O</I>(<I>g</I>(<I>n</I>)) implies l<I>g</I>(<I>f</I>(<I>n</I>))<I> = O</I>(<I>lg(g</I>(<I>n</I>))), where <I>lg(g</I>(<I>n</I>)) &gt; 0 and <I>f</I>(<I>n</I>) <img src="../images/gteq.gif"> 1 for all sufficiently large <I>n</I>.<P>
<I><B>d.</I></B>     <I>f</I>(<I>n</I>)<I> = O(g(n)) </I>implies 2<I><SUP>f(n)</SUP> = O(2<SUP>g(n)</SUP>).</I><P>
<I><B>e.</I></B>     <I>f</I>(<I>n</I>)<I> = O </I>((<I>f</I>(<I>n</I>))<I><SUP>2</I></SUP>)<I>.</I><P>
<I><B>f.</I></B>     <I>f</I>(<I>n</I>)<I> = O</I>(<I>g</I>(<I>n</I>)) implies <I>g</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>f</I>(<I>n</I>)).<P>
<I><B>g.</I></B>     <I>f</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>f</I>(<I>n/2</I>)).<P>
<I><B>h.</I></B>     <I>f</I>(<I>n</I>)<I> + o</I>(<I>f</I>(<I>n</I>)) = <img src="../images/bound.gif">(<I>f </I>(<I>n</I>)).<P>
<a name="06fd_11b5">2-5     Variations on O and <img src="../images/omega12.gif"><a name="06fd_11b5"><P>
<a name="06fd_11aa"><a name="06fd_11ab"><a name="06fd_11ac"><a name="06fd_11ad">Some authors define <img src="../images/omega12.gif"> in a slightly different way than we do; let's use <img src="39_b.gif"> (read &quot;omega infinity&quot;) for this alternative definition. We say that <img src="39_c.gif"> if there exists a positive constant <I>c</I> such that <I>f</I>(<I>n</I>) <img src="../images/gteq.gif"> <I>cg</I>(<I>n</I>) <img src="../images/gteq.gif"> 0 for infinitely many integers <I>n</I>.<P>
<I><B>a.</I></B>     Show that for any two functions <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) that are asymptotically nonnegative, either <I>f</I>(<I>n</I>) = <I>O</I>(<I>g</I>(<I>n</I>)) or <I>f</I>(<I>n</I>) = <img src="39_d.gif"> (<I>g</I>(<I>n</I>)) or both, whereas this is not true if we use <img src="../images/omega12.gif"> in place of <img src="39_e.gif"><P>
<I><B>b.</I></B>     Describe the potential advantages and disadvantages of using <img src="39_f.gif"> instead of <img src="../images/omega12.gif"> to characterize the running times of programs.<P>
<a name="06fd_11ae">Some authors also define <I>O</I> in a slightly different manner; let's use <I>O</I>'<I> for the alternative definition. We say that </I>f<I>(</I>n<I>) = </I>O<I>'</I>(<I>g</I>(<I>n</I>)) if and only if<I> </I><img src="../images/sglvrt.gif">f<I>(</I>n<I>)<img src="../images/sglvrt.gif"> = O</I>'<I>(</I>g(n<I>))</I>.<P>
<I><B>c.</I>     </B>What happens to each direction of the &quot;if and only if&quot; in Theorem 2.1 under this new definition?<P>
Some authors define <img src="../images/sftoh.gif"> (read &quot;soft-oh&quot;) to mean <I>O</I> with logarithmic factors ignored:<P>
<img src="../images/sftoh.gif">(<I>g</I>(<I>n</I>)) = {<I>f</I>(<I>n</I>): there exist positive constants <I>c, k,</I> and <I>n</I><SUB>0</SUB> such that<P>
0<img src="../images/lteq12.gif"> <I>f</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cg</I>(<I>n</I>)1<I>g<SUP>k</I></SUP>(<I>n</I>) for all <I>n</I> <img src="../images/gteq.gif"> <I>n</I><SUB>0</SUB>}.<P>
<I><B>d.</I></B>     Define <img src="40_a.gif"> in a similar manner. Prove the corresponding analog to Theorem 2.1.<P>
<a name="06fd_11b6">2-6     Iterated functions<a name="06fd_11b6"><P>
<a name="06fd_11af">The iteration operator &quot;*&quot; used in the 1g* function can be applied to monotonically increasing functions over the reals. For a function &acirc; satisfying <I>f</I>(<I>n</I>)<I> &lt; n</I>, we define the function <I>f</I><SUP>(i)</SUP> recursively for nonnegative integers <I>i</I> by<P>
<img src="40_b.gif"><P>
For a given constant <I>c</I> <img src="../images/memof12.gif"> <B>R</B>, we define the iterated function <img src="40_c.gif"> by<P>
<img src="40_d.gif"><P>
which need not be well-defined in all cases. In other words, the quantity <img src="40_e.gif">(<I>n</I>) is the number of iterated applications of the function &acirc; required to reduce its argument down to <I>c</I> or less.<P>
For each of the following functions <I>f </I>(<I>n</I>) and constants <I>c</I>, give as tight a bound as possible on <img src="40_f.gif">(<I>n</I>).<P>
<img src="40_g.gif"><P>
<P>







<h1>Chapter notes</h1><P>
Knuth [121] traces the origin of the <I>O</I>-notation to a number-theory text by P. Bachmann in 1892. The <I>o</I>-notation was invented by E. Landau in 1909 for his discussion of the distribution of prime numbers. The <img src="../images/omega12.gif"><B> </B>and <img src="../images/bound.gif"> notations were advocated by Knuth [124] to correct the popular, but technically sloppy, practice in the literature of using <I>O</I>-notation for both upper and lower bounds. Many people continue to use the <I>O</I>-notation where the <img src="../images/bound.gif">-notation is more technically precise. Further discussion of the history and development of asymptotic notations can be found in Knuth[121, 124] and Brassard and Bratley [33]. <P>
Not all authors define the asymptotic notations in the same way, although the various definitions agree in most common situations. Some of the alternative definitions encompass functions that are not asymptotically nonnegative, as long as their absolute values are appropriately bounded.<P>
Other properties of elementary mathematical functions can be found in any good mathematical reference, such as Abramowitz and Stegun [1] or Beyer [27], or in a calculus book, such as Apostol [12] or Thomas and Finney [192]. Knuth [121] contains a wealth of material on discrete mathematics as used in computer science.<P>
<P>


<P>
<P>
<center>Go to <a href="chap03.htm">Chapter 3</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>