page510.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 78 行
HTML
78 行
<HTML><HEAD><TITLE>A Lower Bound on Sorting</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="tex2html7029" HREF="page511.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7027" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7021" HREF="page509.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7031" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0015700000000000000000">A Lower Bound on Sorting</A></H1><P>The preceding sections presentthree <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > sorting algorithms--quicksort, heapsort, and the two-way merge sort.But is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > the best we can do?In this section we answer the question by showing thatany sorting algorithm that sorts using only binary comparisonsmust make <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60159" SRC="img527.gif" > such comparisons.If each binary comparison takes a constant amount of time,then running time for any such sorting algorithm is also <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60159" SRC="img527.gif" >.<P>Consider the problem of sorting the sequence <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69691" SRC="img2097.gif" >comprised of three distinct items.That is, <IMG WIDTH=143 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69693" SRC="img2098.gif" >.Figure <A HREF="page510.html#figcomparison"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates a possible sorting algorithmin the form of a <em>decision tree</em><A NAME=44438> </A>.Each node of the decision tree represents one binary comparison.That is, in each node of the tree,exactly two elements of the sequence are compared.Since there are exactly two possible outcomes for each comparison,each non-leaf node of the binary tree has degree two.<P><P><A NAME="44978"> </A><A NAME="figcomparison"> </A> <IMG WIDTH=575 HEIGHT=284 ALIGN=BOTTOM ALT="figure44439" SRC="img2099.gif" ><BR><STRONG>Figure:</STRONG> A decision tree for comparison sorting.<BR><P><P>For example, suppose that <I>a</I><I><</I><I>b</I><I><</I><I>c</I>.Consider how the algorithm shown in Figure <A HREF="page510.html#figcomparison"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> discovers this. The first comparison compares <I>a</I> and <I>b</I> which reveals that <I>a</I><I><</I><I>b</I>.The second comparison compares <I>a</I> and <I>c</I> to find that <I>a</I><I><</I><I>c</I>.At this point it has been determined that <I>a</I><I><</I><I>b</I> and <I>a</I><I><</I><I>c</I>--the relative order of <I>b</I> and <I>c</I> is not yet known.Therefore, one more comparison is required to determine that <I>b</I><I><</I><I>c</I>.Notice that the algorithm shown in Figure <A HREF="page510.html#figcomparison"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> works correctlyin all cases because every possible permutation of the sequence <I>S</I>appears as a leaf node in the decision tree.Furthermore, the number of comparisons required in the worst caseis equal to the height of the decision tree!<P>Any sorting algorithm that usesonly binary comparisons can be represented by a binary decision tree.Furthermore, it is the height of the binary decision tree thatdetermines the worst-case running time of the algorithm.In general, the size and shape of the decision tree depends onthe sorting algorithm and the number of items to be sorted.<P>Given an input sequence of <I>n</I> items to be sorted,every binary decision tree that correctly sorts the input sequencemust have <em>at least</em> <I>n</I>! leaves--one for each permutation of the input.Therefore, it follows directly from Theorem <A HREF="page256.html#theoremtreesiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>that the height of the binary decision tree is <em>at least</em> <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69755" SRC="img2100.gif" >:<P> <IMG WIDTH=500 HEIGHT=174 ALIGN=BOTTOM ALT="eqnarray44986" SRC="img2101.gif" ><P><P>Since the height of the decision tree is <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60159" SRC="img527.gif" >,the number of comparisons done byany sorting algorithm that sorts using only binary comparisonsis <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60159" SRC="img527.gif" >.Assuming each comparison can be done in constant time,the running time of any such sorting algorithm is <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60159" SRC="img527.gif" >.<P><HR><A NAME="tex2html7029" HREF="page511.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7027" HREF="page478.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7021" HREF="page509.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7031" 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 + -
显示快捷键?