📄 page495.html
字号:
<HTML><HEAD><TITLE>Average Running Time</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="tex2html6865" HREF="page496.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6863" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6857" HREF="page494.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6867" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015440000000000000000">Average Running Time</A></H2><P>To determine the average running time for the quicksort algorithm,we shall assume that each element of the sequence has an equal chanceof being selected for the pivot.Therefore, if <I>i</I> is the number of elements in a sequence of length <I>n</I>less than the pivot,then <I>i</I> is uniformly distributed in the interval [0,<I>n</I>-1].Consequently, the average value of <IMG WIDTH=140 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline69427" SRC="img2053.gif" >.Similarly, the average the value of <IMG WIDTH=252 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline69429" SRC="img2054.gif" >.To determine the average running time,we rewrite Equation <A HREF="page492.html#eqnsortingii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> thus:<P><A NAME="eqnsortingiii"> </A> <IMG WIDTH=506 HEIGHT=102 ALIGN=BOTTOM ALT="eqnarray37704" SRC="img2055.gif" ><P><P>To solve this recurrence we consider the case <I>n</I><I>></I>2and then multiply Equation <A HREF="page495.html#eqnsortingiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by <I>n</I> to get<P> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation37724" SRC="img2056.gif" ><P>Since this equation is valid for any <I>n</I><I>></I>2,by substituting <I>n</I>-1 for <I>n</I> we can also write<P><A NAME="eqnsortingiv"> </A> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation37728" SRC="img2057.gif" ><P>which is valid for <I>n</I><I>></I>3.Subtracting Equation <A HREF="page495.html#eqnsortingiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> from Equation <A HREF="page495.html#eqnsortingiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives<P> <IMG WIDTH=413 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69415" SRC="img2058.gif" ><P>which can be rewritten as<P><A NAME="eqnsortingv"> </A> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="equation37735" SRC="img2059.gif" ><P><P>Equation <A HREF="page495.html#eqnsortingv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> can be solved by telescoping like this:<P><A NAME="eqnsortingvii"> </A><A NAME="eqnsortingvi"> </A> <IMG WIDTH=507 HEIGHT=274 ALIGN=BOTTOM ALT="eqnarray37747" SRC="img2060.gif" ><P>Adding together Equation <A HREF="page495.html#eqnsortingvi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> through Equation <A HREF="page495.html#eqnsortingvii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives<P> <IMG WIDTH=500 HEIGHT=143 ALIGN=BOTTOM ALT="eqnarray37793" SRC="img2061.gif" ><P>where <IMG WIDTH=36 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69443" SRC="img2062.gif" > is the <IMG WIDTH=60 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline69445" SRC="img2063.gif" ><em>harmonic number</em><A NAME=37821> </A>.Finally, multiplying through by <I>n</I>+1 gives<P> <IMG WIDTH=359 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69416" SRC="img2064.gif" ><P><P>In Section <A HREF="page46.html#secmodelharmonic"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> it is shown that <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63999" SRC="img1213.gif" >,where <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64001" SRC="img1214.gif" >is called <em>Euler's constant</em><A NAME=37825> </A>.Thus, we get that the average running time of quicksort is<P> <IMG WIDTH=500 HEIGHT=41 ALIGN=BOTTOM ALT="eqnarray37826" SRC="img2065.gif" ><P>Table <A HREF="page495.html#tblsortingexchange"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizes the asymptotic running timesfor the quicksort method and compares it to those of bubble sort.Notice that the best-case and average case running timesfor the quicksort algorithm have the same asymptotic bound!<P><P><A NAME="37830"> </A><P> <A NAME="tblsortingexchange"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> running time</TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><P> algorithm </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> best case </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> average case </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> worst case </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>bubble sort </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> quicksort (random pivot selection) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Running times for exchange sorting.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html6865" HREF="page496.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6863" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6857" HREF="page494.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6867" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -