page52.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 167 行 · 第 1/2 页

<P> <IMG WIDTH=500 HEIGHT=124 ALIGN=BOTTOM ALT="eqnarray1025" SRC="img174.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img174.gif"  ><P>
The substitution stops when <I>k</I>=<I>j</I>.
Thus,
<P> <IMG WIDTH=500 HEIGHT=88 ALIGN=BOTTOM ALT="eqnarray1031" SRC="img175.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img175.gif"  ><P>
Note that if  <IMG WIDTH=45 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58795" SRC="img171.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img171.gif"  >, then  <IMG WIDTH=68 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline58809" SRC="img176.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img176.gif"  >.
In this case, running time of Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is  <IMG WIDTH=148 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58811" SRC="img177.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img177.gif"  >.
<P>
The preceding result is, in fact, the best case--in all
but the last two recursive calls of the function, <I>n</I> was even.
Interestingly enough, there is a corresponding worst-case scenario.
Suppose  <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58815" SRC="img178.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img178.gif"  > for some value of <I>k</I><I>&gt;</I>0.
Clearly <I>n</I> is odd, since it is one less than  <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif"  >
which is a power of two and even.
Now consider  <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58823" SRC="img180.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img180.gif"  >:
<P> <IMG WIDTH=500 HEIGHT=62 ALIGN=BOTTOM ALT="eqnarray1034" SRC="img181.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img181.gif"  ><P>
Hence,  <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58823" SRC="img180.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img180.gif"  > is also odd!
<P>
For example, suppose <I>n</I> is 31 ( <IMG WIDTH=40 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58829" SRC="img182.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img182.gif"  >).
To compute  <IMG WIDTH=21 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58753" SRC="img163.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img163.gif"  >, Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> calls itself
recursively to compute  <IMG WIDTH=21 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58833" SRC="img183.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img183.gif"  >,  <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58835" SRC="img184.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img184.gif"  >,  <IMG WIDTH=15 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58837" SRC="img185.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img185.gif"  >,  <IMG WIDTH=14 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58839" SRC="img186.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img186.gif"  >, and finally,  <IMG WIDTH=15 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline58841" SRC="img187.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img187.gif"  >--all but the last of which are odd powers of <I>x</I>.
<P>
For  <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58815" SRC="img178.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img178.gif"  >, Equation&nbsp;<A HREF="page52.html#eqnmodelpowtime" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#eqnmodelpowtime"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives
<P> <IMG WIDTH=385 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath58730" SRC="img188.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img188.gif"  ><P>
Solving this recurrence by repeated substitution we get
<P> <IMG WIDTH=500 HEIGHT=124 ALIGN=BOTTOM ALT="eqnarray1042" SRC="img189.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img189.gif"  ><P>
The substitution stops when <I>k</I>=<I>j</I>.
Thus,
<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray1048" SRC="img190.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img190.gif"  ><P>
Note that if  <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58815" SRC="img178.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img178.gif"  >, then  <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58851" SRC="img191.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img191.gif"  >.
In this case, running time of Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is  <IMG WIDTH=177 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58853" SRC="img192.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img192.gif"  >.
<P>
Consider now what happens for an arbitrary value of <I>n</I>.
Table&nbsp;<A HREF="page52.html#tblcalls" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#tblcalls"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows the recursive calls made by
Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> in computing  <IMG WIDTH=15 HEIGHT=10 ALIGN=BOTTOM ALT="tex2html_wrap_inline58739" SRC="img159.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img159.gif"  > for various values of <I>n</I>.
<P>
<P><A NAME="1157">&#160;</A>
<P>
    <A NAME="tblcalls">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=LEFT>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	    <I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=79 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58863" SRC="img193.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img193.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> powers computed recursively </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=22 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58865" SRC="img194.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img194.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=37 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58867" SRC="img195.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img195.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=37 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58869" SRC="img196.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img196.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=53 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58871" SRC="img197.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img197.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=52 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58873" SRC="img198.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img198.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=52 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58875" SRC="img199.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img199.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=52 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58877" SRC="img200.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img200.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=67 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58879" SRC="img201.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img201.gif"  > </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Recursive calls made in Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A></CAPTION></TABLE>
</P></DIV><P>
<P>
By inspection we determine that the number of recursive calls made
in which the second argument is non-zero is  <IMG WIDTH=79 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58863" SRC="img193.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img193.gif"  >.
Furthermore, depending on whether the argument is odd or even,
each of these calls contributes either 18 or 20 cycles.
The pattern emerging in Table&nbsp;<A HREF="page52.html#tblpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#tblpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> suggests that,
on average just as many of the recursive calls result in an even
number as result in an odd one.
The final call (zero argument) adds another 5 cycles.
So, on average, we can expect the running time of Program&nbsp;<A HREF="page52.html#progpowerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page52.html#progpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
to be
<P><A NAME="eqnmodelpower">&#160;</A> <IMG WIDTH=500 HEIGHT=17 ALIGN=BOTTOM ALT="equation1072" SRC="img202.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img202.gif"  ><P><HR><A NAME="tex2html2535" HREF="page53.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page53.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2533" HREF="page47.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page47.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2527" HREF="page51.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page51.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2537" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2538" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>