?? page200.html
字號:
<HTML>
<HEAD>
<TITLE>Analysis</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4381" HREF="page201.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4379" HREF="page198.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page198.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4375" HREF="page199.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4383" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4384" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION008242000000000000000">Analysis</A></H3>
<P>
The proof of the correctness of Program <A HREF="page199.html#progapp04cc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html#progapp04cc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is left as an exercise for the reader (Exercise <A HREF="page201.html#exerciselistsproof" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html#exerciselistsproof"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
We discuss here the running time analysis of the algorithm,
as there are some subtle points to remember which
lead to a result that may be surprising.
<P>
Consider the addition of a polynomial <I>p</I>(<I>x</I>) with
its 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 polynomial
is that it <em>has no terms</em>!
In this case,
exactly <I>n</I> iterations of the main loop are done (lines 7-29).
Furthermore, zero iterations of the second
and the third loops are required (lines 30-35 and 36-41).
Since the result has no terms,
there will be no calls to the <tt>Insert</tt> function.
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>) is
less than the smallest exponent in <I>q</I>(<I>x</I>).
Consequently, there is no power of <I>x</I> which the two polynomials
have 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 7-29) are done.
In each of these iterations,
exactly one new term is inserted into the result
by calling the <tt>Insert</tt> function.
Since all of the terms of <I>p</I>(<I>x</I>) will be exhausted when the main loop
is finished, there will be no iterations of the second loop (lines 30-35).
However, there will be exactly <I>m</I> iterations of the third loop
(lines 36-41) in each of which one new term is inserted into the result
by calling the <tt>Insert</tt> function.
<P>
Altogether, <I>l</I>+<I>m</I> calls to the <tt>Insert</tt> will be made.
It was shown earlier that the running time for the insert function 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="displaymath62038" SRC="img865.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img865.gif" ><P>
<P>
Consequently, the worst case running time
for the polynomial addition given in Program <A HREF="page199.html#progapp04cc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html#progapp04cc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.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 account
of the order in which the terms of the result are computed.
I.e., the <tt>Insert</tt> function repeatedly searches the sorted list
for 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="page199.html#progapp04cc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html#progapp04cc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
all of the calls to the <tt>Insert</tt> function by
<PRE>result.linkedList.Append (...);</PRE>
the total running time can be reduced to <I>O</I>(<I>n</I>) from <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.gif" >!
<P>
<HR><A NAME="tex2html4381" HREF="page201.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page201.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4379" HREF="page198.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page198.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4375" HREF="page199.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page199.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4383" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4384" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -