page74.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 107 行
HTML
107 行
<HTML><HEAD><TITLE>Example-Prefix Sums</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="tex2html2061" HREF="page75.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2059" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2053" HREF="page73.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2063" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003420000000000000000">Example-Prefix Sums</A></H2><P>In this section, we will determine a tight big-oh boundon the running time of a program to compute the series of sums <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59807" SRC="img457.gif" >, <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif" >, ..., <IMG WIDTH=32 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline58141" SRC="img148.gif" >, where<P> <IMG WIDTH=289 HEIGHT=47 ALIGN=BOTTOM ALT="displaymath59805" SRC="img458.gif" ><P>An algorithm to compute this series of summationsis given in Program <A HREF="page74.html#progexamplek"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Table <A HREF="page74.html#tblprefixsumsc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizes the running time calculation.<P><P><A NAME="2250"> </A><A NAME="progexamplek"> </A> <IMG WIDTH=575 HEIGHT=202 ALIGN=BOTTOM ALT="program2008" SRC="img461.gif" ><BR><STRONG>Program:</STRONG> Program to compute <IMG WIDTH=53 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline59813" SRC="img459.gif" > for <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59815" SRC="img460.gif" >.<BR><P><P><P><A NAME="2252"> </A><P> <A NAME="tblprefixsumsc"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=LEFT><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> statement </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> time </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59819" SRC="img462.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59819" SRC="img462.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59819" SRC="img462.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=164 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59825" SRC="img463.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=164 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59825" SRC="img463.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=164 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59825" SRC="img463.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 9 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59819" SRC="img462.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59819" SRC="img462.gif" > </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time of Program <A HREF="page74.html#progexamplek"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>Usually the easiest way to analyze program which contains nested loopsis to start with the body of the inner-most loop.In Program <A HREF="page74.html#progexamplek"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the inner-most loop comprises lines 6-8.In all, a constant amount of work is done--this includesthe conditional test (line 6),the loop body (line 7) andthe incrementing of the loop index (line 8).<P>For a given value of <I>j</I>,the inner-most loop is done a total <I>j</I>+1 times.And since the outer loop is done for <IMG WIDTH=153 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59841" SRC="img464.gif" >,in the worst case, the inner-most loop is done <I>n</I> times.Therefore, the contribution of the inner loop to the runningtime of one iteration of the outer loop is <I>O</I>(<I>n</I>).<P>The rest of the outer loop (lines 4, 5, 9 and 10)does a constant amount of work in each iteration.This constant work is dominated by the <I>O</I>(<I>n</I>) of the inner loop.The outer loop is does exactly <I>n</I> iterations.Therefore, the total running time of the program is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.<P>But is this a tight big oh bound?We might suspect that it is not,because of the worst-case assumption we madein the analysis concerning the number of times the inner loop is executed.The inner-most loop is done exactly <I>j</I>+1 timesfor <IMG WIDTH=153 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59841" SRC="img464.gif" >.However, we did the calculation assuming the inner loop is done <I>O</I>(<I>n</I>) times,in each iteration of the outer loop.Unfortunately, in order to determine whether our answer is a tight bound,we must determine more precisely the actual running time of the program.<P>However, there is one approximate calculation that we can easily make.If we observe that the running time will be dominated by thework done in the inner-most loop,and that the work done in one iteration of the inner-most loop is constant,then all we need to do is to determine exactly the number of timesthe inner loop is actually executed.This is given by:<P> <IMG WIDTH=500 HEIGHT=114 ALIGN=BOTTOM ALT="eqnarray2034" SRC="img465.gif" ><P>Therefore, the result <IMG WIDTH=95 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59859" SRC="img466.gif" > is a tight, big-oh boundon the running time of Program <A HREF="page74.html#progexamplek"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><HR><A NAME="tex2html2061" HREF="page75.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2059" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2053" HREF="page73.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2063" 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 + -
显示快捷键?