page492.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 50 行
HTML
50 行
<HTML><HEAD><TITLE>Running Time Analysis</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="tex2html6832" HREF="page493.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6830" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6824" HREF="page491.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6834" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015430000000000000000">Running Time Analysis</A></H2><P>The running time of the recursive <tt>quicksort</tt> method(Program <A HREF="page491.html#progquickSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>)is given by<P><A NAME="eqnsortingi"> </A> <IMG WIDTH=521 HEIGHT=48 ALIGN=BOTTOM ALT="equation37655" SRC="img2043.gif" ><P>where <I>n</I> is the number of elements in sequence to be sorted, <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69381" SRC="img2044.gif" > is the running time of the <tt>selectPivot</tt> method,and <I>i</I> is the number of elements which end up to the left of the pivot, <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69385" SRC="img2045.gif" >.<P>The running time of <tt>quicksort</tt> is affected by the <tt>selectPivot</tt>method in two ways:First, the value of the pivot chosen affects the sizes of the subsequences.That is, the pivot determines the value <I>i</I> in Equation <A HREF="page492.html#eqnsortingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Second, the running time of the <tt>selectPivot</tt> method itself, <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69381" SRC="img2044.gif" >,must be taken into account.Fortunately, if <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69391" SRC="img2046.gif" >,we can ignore its running time because there is already an <I>O</I>(<I>n</I>) termin the expression.<P>In order to solve Equation <A HREF="page492.html#eqnsortingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we assume that <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69391" SRC="img2046.gif" >and then drop the <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >s from the recurrence to get<P><A NAME="eqnsortingii"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation37666" SRC="img2047.gif" ><P>Clearly the solution depends on the value of <I>i</I>.<P><BR> <HR><UL> <LI> <A NAME="tex2html6835" HREF="page493.html#SECTION0015431000000000000000">Worst-Case Running Time</A><LI> <A NAME="tex2html6836" HREF="page494.html#SECTION0015432000000000000000">Best-Case Running Time</A></UL><HR><A NAME="tex2html6832" HREF="page493.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6830" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6824" HREF="page491.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6834" 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 + -
显示快捷键?