page47.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 48 行
HTML
48 行
<HTML><HEAD><TITLE>Best-Case and Worst-Case 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="tex2html1746" HREF="page48.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1744" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1738" HREF="page46.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1748" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002190000000000000000">Best-Case and Worst-Case Running Times</A></H2><P>In Section <A HREF="page45.html#secmodelavg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we derived the average runningtime of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> which finds the largest element of an array.In order to do this we had to determine the probability that a certainprogram statement is executed.To do this, we made an assumption aboutthe <em>average</em> input to the program.<P>The analysis can be significantly simplified if we simply wishto determine the <em>worst case</em> running time.For Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the worst-case scenario occurs when line 6 is executed in every iterationof the loop.We saw that this corresponds to the case in which the input array isordered from smallest to largest.In terms of Equation <A HREF="page45.html#eqnmodelavg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,this occurs when <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57889" SRC="img88.gif" >.Thus, the worst-case running time is given by<P> <IMG WIDTH=500 HEIGHT=154 ALIGN=BOTTOM ALT="eqnarray817" SRC="img123.gif" ><P><P>Similarly, the <em>best-case</em> running time occurs when line 6is never executed.This corresponds to the case in which the input array is ordered fromlargest to smallest.This occurs when <IMG WIDTH=44 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57891" SRC="img89.gif" > andbest-case running time is<P> <IMG WIDTH=500 HEIGHT=70 ALIGN=BOTTOM ALT="eqnarray826" SRC="img124.gif" ><P><P>In summary we have the following results for the running time ofProgram <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>:<P> <IMG WIDTH=360 HEIGHT=135 ALIGN=BOTTOM ALT="gather833" SRC="img125.gif" ><P><HR><A NAME="tex2html1746" HREF="page48.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1744" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1738" HREF="page46.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1748" 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 + -
显示快捷键?