📄 page486.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 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="tex2html6764" HREF="page487.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6762" HREF="page483.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6756" HREF="page485.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html6766" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015320000000000000000">Average Running Time</A></H2><A NAME="secsortingavg">&#160;</A><P>The best case running time of insertion sorting is <I>O</I>(<I>n</I>)but the worst-case running time is  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  >.Therefore, we might suspect that the average running timefalls somewhere in between.In order to determine it,we must define more precisely what we mean by the <em>average</em> running time.A simple definition of average running time is to say that it isthe running time needed to sort the average sequence.But what is the average sequence?<P>The usual way to determine the average running time of a sorting algorithmis to consider only sequences that contain no duplicates.Since every sorted sequence of length <I>n</I>is simply a permutation of an unsorted one,we can represent every such sequence by a permutation ofthe sequence  <IMG WIDTH=129 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69093" SRC="img2003.gif"  >.When computing the average running time,we assume that every permutation is equally likely.Therefore, the average running time of a sorting algorithmis the running time averaged over all permutations of the sequence <I>S</I>.<P>Consider a permutation  <IMG WIDTH=160 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68937" SRC="img1978.gif"  >of the sequence <I>S</I>.An <em>inversion</em><A NAME=35100>&#160;</A>in <I>P</I> consists of two elements,say  <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif"  > and  <IMG WIDTH=14 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69105" SRC="img2004.gif"  >,such that  <IMG WIDTH=49 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline69107" SRC="img2005.gif"  > but <I>i</I><I>&lt;</I><I>j</I>.That is, an inversion in <I>P</I> is a pair of elements that are in the wrong order.For example, the permutation  <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69113" SRC="img2006.gif"  > contains three inversions--(4,3), (4,2), and (3,2).The following theorem tells us how many inversions we can expectin the average sequence:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremsortingi">&#160;</A>The average number of inversions in a permutation of <I>n</I>distinct elements is <I>n</I>(<I>n</I>-1)/4.</BLOCKQUOTE><P>	extbfProofLet <I>S</I> be an arbitrary sequence of <I>n</I> distinct elementsand let  <IMG WIDTH=19 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline69129" SRC="img2007.gif"  > be the same sequence, but in reverse.<P>For example, if  <IMG WIDTH=156 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68897" SRC="img1975.gif"  >,then  <IMG WIDTH=201 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline69133" SRC="img2008.gif"  >.<P>Consider any pair of distinct elements in S,say  <IMG WIDTH=11 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68959" SRC="img1985.gif"  > and  <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68961" SRC="img1986.gif"  > where  <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68955" SRC="img1983.gif"  >.There are two distinct possibilities:Either  <IMG WIDTH=46 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline69141" SRC="img2009.gif"  >, in which case  <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69143" SRC="img2010.gif"  > is an inversion in  <IMG WIDTH=19 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline69129" SRC="img2007.gif"  >;or  <IMG WIDTH=46 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline69147" SRC="img2011.gif"  >, in which case  <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69149" SRC="img2012.gif"  > is an inversion in <I>S</I>.Therefore, every pair contributes exactlyone inversion either to <I>S</I> or to  <IMG WIDTH=19 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline69129" SRC="img2007.gif"  >.<P>The total number of pairs in <I>S</I> is  <IMG WIDTH=116 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline69159" SRC="img2013.gif"  >.Since every such pair contributes an inversion either to <I>S</I> or to  <IMG WIDTH=19 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline69129" SRC="img2007.gif"  >,we expect <em>on average</em> that half of the inversions will appear in <I>S</I>.Therefore, the average number of inversions in a sequence of <I>n</I>distinct elements is <I>n</I>(<I>n</I>-1)/4.<P>What do inversions have to do with sorting?As a list is sorted, inversions are removed.In fact, since the inner loop of the insertion sort methodswaps <em>adjacent</em> array elements,inversions are removed <em>one at a time</em>!Since a swap takes constant time,and since the average number of inversions is <I>n</I>(<I>n</I>-1)/4,the <em>average</em> running timefor the insertion sort method is  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  >.<P><HR><A NAME="tex2html6764" HREF="page487.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6762" HREF="page483.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6756" HREF="page485.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html6766" 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 &#169; 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 + -