page72.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 109 行
HTML
109 行
<HTML><HEAD><TITLE>Asymptotic Analysis of Algorithms</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html2033" HREF="page73.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2031" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2025" HREF="page71.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2035" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION003400000000000000000">Asymptotic Analysis of Algorithms</A></H1><P>The previous chapter presents a detailed model of the computerwhich involves a number of different timing parameters-- <IMG WIDTH=35 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57635" SRC="img7.gif" >, <IMG WIDTH=33 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57637" SRC="img8.gif" >, <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline57647" SRC="img10.gif" >, <IMG WIDTH=16 HEIGHT=10 ALIGN=MIDDLE ALT="tex2html_wrap_inline57649" SRC="img11.gif" >, <IMG WIDTH=15 HEIGHT=12 ALIGN=MIDDLE ALT="tex2html_wrap_inline57651" SRC="img12.gif" >, <IMG WIDTH=16 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57653" SRC="img13.gif" >, <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57655" SRC="img14.gif" >, <IMG WIDTH=26 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57659" SRC="img16.gif" >, <IMG WIDTH=42 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57661" SRC="img17.gif" >, <IMG WIDTH=29 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58033" SRC="img126.gif" >, and <IMG WIDTH=18 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57695" SRC="img31.gif" >.We show that keeping track of the details is messy and tiresome.So we simplify the model by measuring time in clock cycles,and by assuming that each of the parameters is equal to one cycle.Nevertheless, keeping track of and carefully counting all the cyclesis still a tedious task.<P>In this chapter we introduce the notion of asymptotic bounds,principally big oh, and examine the properties of such bounds.As it turns out, the rules for computing and manipulating big oh expressionsgreatly simplify the analysis of the running time of a programwhen all we are interested in is its asymptotic behavior.<P>For example,consider the analysis of the running time of Program <A HREF="page72.html#progexamplej"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,which is just Program <A HREF="page41.html#progexampleb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> again,an algorithm to evaluate a polynomial using Horner's rule.<P><P><A NAME="2246"> </A><A NAME="progexamplej"> </A> <IMG WIDTH=575 HEIGHT=142 ALIGN=BOTTOM ALT="program1913" SRC="img440.gif" ><BR><STRONG>Program:</STRONG> Program <A HREF="page41.html#progexampleb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> again.<BR><P><P><P><A NAME="2248"> </A><P> <A NAME="tblhorner2c"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> detailed model </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> simple </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> big oh</TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> model </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=135 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline57697" SRC="img32.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=132 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline57713" SRC="img37.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57677" SRC="img23.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3<I>n</I>+3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=250 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57717" SRC="img38.gif" > </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=174 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57719" SRC="img39.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4<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> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=96 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline57683" SRC="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=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59697" SRC="img441.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=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59703" SRC="img442.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=307 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57725" SRC="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 <A HREF="page72.html#progexamplej"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>Table <A HREF="page72.html#tblhorner2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the running time analysisof Program <A HREF="page72.html#progexamplej"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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:Lines 2, 3, and 7 execute in a constant amount of time;4, 5, and 6 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 runningtime of the algorithm.And this fundamental result <em>does not depend upon the characteristicsof 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 timeof a particular program.(Recall Fallacies <A HREF="page66.html#fallacyiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page66.html#fallacyiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P><BR> <HR><UL> <LI> <A NAME="tex2html2036" HREF="page73.html#SECTION003410000000000000000">Rules For Big Oh Analysis of Running Time</A><LI> <A NAME="tex2html2037" HREF="page74.html#SECTION003420000000000000000">Example-Prefix Sums</A><LI> <A NAME="tex2html2038" HREF="page75.html#SECTION003430000000000000000">Example-Fibonacci Numbers</A><LI> <A NAME="tex2html2039" HREF="page76.html#SECTION003440000000000000000">Example-Bucket Sort</A><LI> <A NAME="tex2html2040" HREF="page77.html#SECTION003450000000000000000">Reality Check</A><LI> <A NAME="tex2html2041" HREF="page78.html#SECTION003460000000000000000">Checking Your Analysis</A></UL><HR><A NAME="tex2html2033" HREF="page73.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2031" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2025" HREF="page71.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2035" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?