page70.html

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

		</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 9<I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=96 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58225" SRC="img25.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img25.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=185 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60243" SRC="img444.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img444.gif"  >
		</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 16<I>n</I>+14 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=141 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60249" SRC="img445.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img445.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=308 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline58267" SRC="img41.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img41.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time of Program&nbsp;<A HREF="page70.html#proghorner2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html#proghorner2c"><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>
Table&nbsp;<A HREF="page70.html#tblhorner2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html#tblhorner2c"><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 running time analysis
of Program&nbsp;<A HREF="page70.html#proghorner2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html#proghorner2c"><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> done in three ways--a detailed analysis, a simplified analysis, and an asymptotic analysis.
In particular, note that all three methods of analysis are in agreement:
Statements&nbsp;3, 4a, and&nbsp;6 execute in a constant amount of time;
4b, 4c, and&nbsp;5 execute in an amount of time which is proportional to <I>n</I>,
plus a constant.
<P>
The most important observation to make is that,
regardless of what the actual constants are,
the asymptotic analysis always produces the same answer!
Since the result does not depend upon the values of the constants,
the asymptotic bound tells us something fundamental about the running
time of the algorithm.
And this fundamental result <em>does not depend upon the characteristics
of the computer and compiler actually used to execute the program</em>!
<P>
Of course, you don't get something for nothing.
While the asymptotic analysis may be significantly easier to do,
all that we get is an upper bound on the running time of the algorithm.
In particular, we know nothing about the <em>actual</em> running time
of a particular program.
(Recall Fallacies&nbsp;<A HREF="page64.html#fallacyiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page64.html#fallacyiii"><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> and&nbsp;<A HREF="page64.html#fallacyiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page64.html#fallacyiv"><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>).
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html2763" HREF="page71.html#SECTION004410000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page71.html#SECTION004410000000000000000">Rules For Big Oh Analysis of Running Time</A>
<LI> <A NAME="tex2html2764" HREF="page72.html#SECTION004420000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page72.html#SECTION004420000000000000000">Example-Prefix Sums</A>
<LI> <A NAME="tex2html2765" HREF="page73.html#SECTION004430000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#SECTION004430000000000000000">Example-Fibonacci Numbers</A>
<LI> <A NAME="tex2html2766" HREF="page74.html#SECTION004440000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#SECTION004440000000000000000">Example-Bucket Sort</A>
<LI> <A NAME="tex2html2767" HREF="page75.html#SECTION004450000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page75.html#SECTION004450000000000000000">Reality Check</A>
<LI> <A NAME="tex2html2768" HREF="page76.html#SECTION004460000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page76.html#SECTION004460000000000000000">Checking Your Analysis</A>
</UL>
<HR><A NAME="tex2html2759" HREF="page71.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page71.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="tex2html2757" HREF="page56.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page56.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="tex2html2751" HREF="page69.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page69.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="tex2html2761" 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="tex2html2762" 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>