page55.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 78 行
HTML
78 行
<HTML><HEAD><TITLE>Example-Geometric Series Summation Yet Again</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="tex2html1836" HREF="page56.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1834" HREF="page49.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1830" HREF="page54.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1838" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002260000000000000000">Example-Geometric Series Summation Yet Again</A></H2><P>In this example we consider the problem of computing a<em>geometric series summation</em><A NAME=1137> </A>for the last time.We have already seen two algorithms to compute this summationin Sections <A HREF="page50.html#secmodelgeometric"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page52.html#secmodelgeometric2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>(Programs <A HREF="page50.html#progexamplef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page52.html#progexampleg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>An algorithm to compute a geometric series summationusing the closed-form expression (Equation <A HREF="page53.html#eqngeometric"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>)is given in Program <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.This algorithm makes use of Program <A HREF="page54.html#progexampleh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to compute <IMG WIDTH=32 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58335" SRC="img200.gif" >.<P><P><A NAME="1218"> </A><A NAME="progexamplei"> </A> <IMG WIDTH=575 HEIGHT=50 ALIGN=BOTTOM ALT="program1146" SRC="img201.gif" ><BR><STRONG>Program:</STRONG> Program to compute <IMG WIDTH=53 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58081" SRC="img133.gif" > using the closed-form expression.<BR><P><P>To determine the average running time of Program <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>we will make use of Equation <A HREF="page54.html#eqnmodelpower"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,which gives the average running time for the <tt>power</tt> methodwhich is called on line 2.In this case, the arguments are <I>x</I> and <I>n</I>+1,so the running time of the call to <tt>power</tt> is <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58343" SRC="img202.gif" >.Adding to this the additional work done on line 2 givesthe average running time for Program <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>:<P> <IMG WIDTH=370 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath58333" SRC="img203.gif" ><P><P>The running times of the three programswhich compute the geometric series summationpresented in this chapter are tabulated belowin Table <A HREF="page55.html#tblgeometricsummary"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and are plotted for <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58345" SRC="img204.gif" > in Figure <A HREF="page55.html#figgeometric"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The plot shows that,according to our simplified model of the computer,Program <A HREF="page52.html#progexampleg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> has the best running time for <I>n</I><I><</I>4.However as <I>n</I> increases,Program <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is clearly the fastest of the threeand Program <A HREF="page50.html#progexamplef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is the slowest for all values of <I>n</I>.<P><P><A NAME="1220"> </A><P> <A NAME="tblgeometricsummary"> </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> program </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> T(n) </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>Program <A HREF="page50.html#progexamplef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=125 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline58353" SRC="img205.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> Program <A HREF="page52.html#progexampleg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 13<I>n</I>+22 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> Program <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=181 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58357" SRC="img206.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Running times of Programs <A HREF="page50.html#progexamplef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page52.html#progexampleg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P><P><A NAME="1361"> </A><A NAME="figgeometric"> </A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure1182" SRC="img207.gif" ><BR><STRONG>Figure:</STRONG> Plot of running time vs. <I>n</I> for Programs <A HREF="page50.html#progexamplef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page52.html#progexampleg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page55.html#progexamplei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<BR><P><HR><A NAME="tex2html1836" HREF="page56.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1834" HREF="page49.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1830" HREF="page54.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1838" 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 + -
显示快捷键?