📄 page202.html
字号:
<HTML><HEAD><TITLE>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="tex2html3527" HREF="page203.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3525" HREF="page200.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3521" HREF="page201.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3529" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007242000000000000000">Analysis</A></H3><P>The proof of the correctness of Program <A HREF="page201.html#progpolynomialAsSortedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is left as an exercise for the reader (Exercise <A HREF="page203.html#exerciselistsproof"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).We discuss here the running time analysis of the algorithm,as there are some subtle points to remember whichlead to a result that may be surprising.<P>Consider the addition of a polynomial <I>p</I>(<I>x</I>) withits arithmetic complement -<I>p</I>(<I>x</I>).Suppose <I>p</I>(<I>x</I>) has <I>n</I> terms.Clearly -<I>p</I>(<I>x</I>) also has <I>n</I> terms.The sum of the polynomials is the zero polynomial.An important characteristic of the zero polynomialis that it <em>has no terms</em>!In this case,exactly <I>n</I> iterations of the main loop are done (lines 19-31).Furthermore, zero iterations of the secondand the third loops are required (lines 32-34 and 35-37).Since the result has no terms,there will be no calls to the <tt>addTerm</tt> method.Therefore, the amount of work done in each iteration is a constant.Consequently, the best case running time is <I>O</I>(<I>n</I>).<P>Consider now the addition of two polynomials, <I>p</I>(<I>x</I>) and <I>q</I>(<I>x</I>),having <I>l</I> and <I>m</I> terms, respectively.Furthermore, suppose that largest exponent in <I>p</I>(<I>x</I>) isless than the smallest exponent in <I>q</I>(<I>x</I>).Consequently, there is no power of <I>x</I> which the two polynomialshave in common.In this case, since <I>p</I>(<I>x</I>) has the lower-order terms,exactly <I>l</I> iterations of the main loop (lines 19-31) are done.In each of these iterations,exactly one new term is inserted into the resultby calling the <tt>addTerm</tt> method.Since all of the terms of <I>p</I>(<I>x</I>) will be exhausted when the main loopis finished, there will be no iterations of the second loop (lines 32-34).However, there will be exactly <I>m</I> iterations of the third loop(lines 35-37) in each of which one new term is inserted into the resultby calling the <tt>addTerm</tt> method.<P>Altogether, <I>l</I>+<I>m</I> calls to the <tt>addTerm</tt> will be made.It was shown earlier that the running time for the insert method is <I>O</I>(<I>k</I>),where <I>k</I> is the number of items in the sorted list.Consequently, the total running time for the <I>l</I>+<I>m</I> insertions is<P> <IMG WIDTH=342 HEIGHT=47 ALIGN=BOTTOM ALT="displaymath61411" SRC="img819.gif" ><P><P>Consequently, the worst case running timefor the polynomial addition given in Program <A HREF="page201.html#progpolynomialAsSortedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >, where <I>n</I>=<I>l</I>+<I>m</I>.This is somewhat disappointing.The implementation is not optimal because it fails to take accountof the order in which the terms of the result are computed.That is, the <tt>addTerm</tt> method repeatedly searches the sorted listfor the correct position at which to insert the next term.But we know that correct position is at the end!By replacing in Program <A HREF="page201.html#progpolynomialAsSortedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>all of the calls to the <tt>addTerm</tt> method by<PRE>self._list._linkedList.append(...)</PRE>the total running time can be reduced to <I>O</I>(<I>n</I>) from <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >!<P><HR><A NAME="tex2html3527" HREF="page203.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3525" HREF="page200.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3521" HREF="page201.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3529" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -