page45.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 69 行
HTML
69 行
<HTML><HEAD><TITLE>Average Running Times</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="tex2html1724" HREF="page46.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1722" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1716" HREF="page44.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1726" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002170000000000000000">Average Running Times</A></H2><A NAME="secmodelavg"> </A><P>In the previous section,we found the function, <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57861" SRC="img82.gif" >,which gives the running time of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>as a function both of number of inputs, <I>n</I>,and of the actual input values.Suppose instead we are interested in a function <IMG WIDTH=73 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline57869" SRC="img83.gif" >which gives the running time <em>on average</em>for <I>n</I> inputs, regardless of the values of those inputs.In other words, if we run Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,a large number of times on a selection of random inputs of length <I>n</I>,what will the average running time be?<P>We can write the sum of the running times given in Table <A HREF="page44.html#tblfindmaxc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>in the following form<P><A NAME="eqnmodelavg"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation558" SRC="img84.gif" ><P>where <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > is the probability that line 6 of the program is executed.The probability <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > is given by<P> <IMG WIDTH=337 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath57863" SRC="img86.gif" ><P>That is, <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > is the probability that the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > array entry, <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" >,is larger than the maximum of all the preceding array entries, <IMG WIDTH=102 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57885" SRC="img87.gif" >.<P>In order to determine <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" >,we need to know (or to assume)something about the distribution of input values.For example, if we know <em>a priori</em> that the array passed to the method<tt>findMaximum</tt> is ordered from smallest to largest,then we know that <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57889" SRC="img88.gif" >.Conversely, if we know that the array is ordered from largest to smallest,then we know that <IMG WIDTH=44 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57891" SRC="img89.gif" >.<P>In the general case, we have no <em>a priori</em> knowledge of thedistribution of the values in the input array.In this case, consider the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > iteration of the loop.In this iteration <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" > is compared with the maximum of the <I>i</I> values, <IMG WIDTH=102 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57885" SRC="img87.gif" > preceding it in the array.Line 6 of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is only executed if <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" > is the largestof the <I>i</I>+1 values <IMG WIDTH=86 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57905" SRC="img90.gif" >.All things being equal,we can say that this will happen with probability 1/(<I>i</I>+1).Thus<P><A NAME="eqnmodelprob"> </A> <IMG WIDTH=500 HEIGHT=77 ALIGN=BOTTOM ALT="eqnarray574" SRC="img91.gif" ><P><P>Substituting this expression for <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > in Equation <A HREF="page45.html#eqnmodelavg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and simplifying the result we get<P><A NAME="eqnmodeltn"> </A> <IMG WIDTH=500 HEIGHT=180 ALIGN=BOTTOM ALT="eqnarray581" SRC="img92.gif" ><P>where <IMG WIDTH=93 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline57911" SRC="img93.gif" >,is the <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" > <em>harmonic number</em><A NAME=601> </A>.<P><HR><A NAME="tex2html1724" HREF="page46.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1722" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1716" HREF="page44.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1726" 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 + -
显示快捷键?