page336.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 65 行
HTML
65 行
<HTML><HEAD><TITLE>Linear Search</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="tex2html5067" HREF="page337.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5065" HREF="page335.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5059" HREF="page335.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5069" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010621000000000000000">Linear Search</A></H3><P>Program <A HREF="page336.html#progmWayTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the naıve versionof the <tt>find</tt> method of the <tt>MWayTree</tt> class.The <tt>find</tt> method takes an objectand locates the item in the search tree which matches the given object.<P><P><A NAME="21036"> </A><A NAME="progmWayTreec"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program20891" SRC="img1306.gif" ><BR><STRONG>Program:</STRONG> <tt>MWayTree</tt> class <tt>find</tt> method (linear search).<BR><P><P>Consider the execution of the <tt>find</tt> method for a node <I>T</I>of a an <I>M</I>-way search tree.Suppose the object of the search is <I>x</I>.Clearly, the search fails when <IMG WIDTH=40 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62991" SRC="img1064.gif" > (lines 4-5).In this case, <tt>None</tt> is returned.<P>Suppose <IMG WIDTH=267 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64803" SRC="img1307.gif" >.The linear search on lines 6-13 considers the keys <IMG WIDTH=31 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63727" SRC="img1171.gif" >, <IMG WIDTH=31 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64807" SRC="img1308.gif" >, <IMG WIDTH=32 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64809" SRC="img1309.gif" >, ..., <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63723" SRC="img1169.gif" >, in that order.If a match is found,the matching object is returned immediately (lines 9-10).<P>Otherwise, when the main loop terminates there are three possibilities:<I>i</I>=0 and <IMG WIDTH=58 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64815" SRC="img1310.gif" >; <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64817" SRC="img1311.gif" > and <IMG WIDTH=92 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63803" SRC="img1182.gif" >; or<I>i</I>=<I>n</I>-1 and <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64823" SRC="img1312.gif" >.In all three cases,the appropriate subtree in which to continue search is <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > (line 14).<P>Clearly the running time of Program <A HREF="page336.html#progmWayTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is determined by the main loop.In the worst case, the loop is executed <I>M</I>-1 times.Therefore, at each node in the search pathat most <I>M</I>-1 object comparisons are done.<P>Consider an unsuccessful search in an <I>M</I>-way search tree.The running time of the <tt>find</tt> method is<P> <IMG WIDTH=358 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64793" SRC="img1313.gif" ><P>in the worst case,where <I>h</I> is the height of the treeand <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63515" SRC="img1154.gif" > is the time required to compare two objects.Clearly, the time for a successful search has the same asymptotic bound.If the tree is balanced and <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64143" SRC="img1239.gif" >,then the running time of Program <A HREF="page336.html#progmWayTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64839" SRC="img1314.gif" >,where <I>K</I> is the number of keys in the tree.<P><HR><A NAME="tex2html5067" HREF="page337.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5065" HREF="page335.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5059" HREF="page335.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5069" 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 + -
显示快捷键?