page44.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 95 行
HTML
95 行
<HTML><HEAD><TITLE>Yet Another example-Finding the Largest Element of an Array</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="tex2html1713" HREF="page45.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1711" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1705" HREF="page43.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1715" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002160000000000000000">Yet Another example-Finding the Largest Element of an Array</A></H2><P>In this section we consider the problem of finding the largestelement of an array.That is, given an array of <I>n</I> non-negative integers, <IMG WIDTH=105 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57823" SRC="img69.gif" >,we wish to find<P> <IMG WIDTH=279 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath57815" SRC="img70.gif" ><P><P>The straightforward way of solving this problem is to perform a<em>linear search</em><A NAME=510> </A> of the array.The linear search algorithm is given in Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and the running times for the various statements are givenin Table <A HREF="page44.html#tblfindmaxc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="655"> </A><A NAME="progexampled"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program513" SRC="img72.gif" ><BR><STRONG>Program:</STRONG> Linear search to find <IMG WIDTH=85 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline57825" SRC="img71.gif" >.<BR><P><P><P><A NAME="657"> </A><P> <A NAME="tblfindmaxc"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> time </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=135 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline57697" SRC="img32.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=88 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline57639" SRC="img9.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=120 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57831" SRC="img73.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=199 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57833" SRC="img74.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=168 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57835" SRC="img75.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=213 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57837" SRC="img76.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=88 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline57639" SRC="img9.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>With the exception of line 6,the running times follow simply from Axioms <A HREF="page38.html#axiomi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page38.html#axiomii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page40.html#axiomv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In particular, note that the body of the loopis executed <I>n</I>-1 times.This means that the conditional test on line 5 is executed <I>n</I>-1 times.However, the number of times line 6 is executed depends onthe data in the array and not just <I>n</I>.<P>If we consider that in each iteration of the loop body,the variable <tt>result</tt> contains the largest array element seen so far,then line 6 will be executed in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > iteration of the looponly if <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57849" SRC="img78.gif" > satisfies the following<P> <IMG WIDTH=309 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath57816" SRC="img79.gif" ><P><P>Thus, the running time of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57757" SRC="img51.gif" >,is a function not only of the number of elements in the array, <I>n</I>,but also of the actual array values, <IMG WIDTH=105 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57823" SRC="img69.gif" >.Summing the entries in Table <A HREF="page44.html#tblfindmaxc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we get<P> <IMG WIDTH=430 HEIGHT=62 ALIGN=BOTTOM ALT="displaymath57817" SRC="img80.gif" ><P>where<P> <IMG WIDTH=500 HEIGHT=65 ALIGN=BOTTOM ALT="eqnarray546" SRC="img81.gif" ><P><P>While this result may be correct,it is not terribly useful.In order to determine the running time of the programwe need to know the number of elements in the array, <I>n</I>,and we need to know the values of the elements in the array, <IMG WIDTH=105 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline57823" SRC="img69.gif" >.Even if we know these data,it turns out that in order to compute the running time of the algorithm, <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57861" SRC="img82.gif" >,we actually have to solve the original problem!<P><HR><A NAME="tex2html1713" HREF="page45.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1711" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1705" HREF="page43.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1715" 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 + -
显示快捷键?