page73.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 65 行
HTML
65 行
<HTML><HEAD><TITLE>Rules For Big Oh Analysis of Running Time</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="tex2html2050" HREF="page74.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2048" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2042" HREF="page72.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2052" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003410000000000000000">Rules For Big Oh Analysis of Running Time</A></H2><P>In this section we present some simple rules for determininga big-oh upper bound on the running time of thebasic compound statements<A NAME=1939> </A> in a Python program.<P><P><A NAME="rulei"> </A> <IMG WIDTH=577 HEIGHT=184 ALIGN=BOTTOM ALT="ruledef1940" SRC="img443.gif" ><P><P>Rule <A HREF="page73.html#rulei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> follows directly from Theorem <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The total running time of a sequence of statements is equal to thesum of the running times of the individual statements.By Theorem <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,when computing the sum of a series of functionsit is the largest one (the <IMG WIDTH=29 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline58753" SRC="img290.gif" >) that determines the bound.<P><P><A NAME="ruleii"> </A> <IMG WIDTH=575 HEIGHT=151 ALIGN=BOTTOM ALT="ruledef1953" SRC="img444.gif" ><P><P><P><A NAME="ruleiii"> </A> <IMG WIDTH=579 HEIGHT=272 ALIGN=BOTTOM ALT="ruledef1963" SRC="img445.gif" ><P><P>Consider the following simple <em>counted do loop</em><A NAME=1979> </A>.<PRE>for i in range(n): <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap59719" SRC="img446.gif" ></PRE>Here <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif" > is the expression ``<tt>n</tt>'',so its running time is constant ( <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59773" SRC="img448.gif" >).Also, the number of iterations is <I>I</I>(<I>n</I>) = <I>n</I>.According to Rule <A HREF="page73.html#ruleiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the running time of the <tt>for</tt> loop is <IMG WIDTH=218 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59777" SRC="img449.gif" >,which simplifies to <IMG WIDTH=176 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59779" SRC="img450.gif" >.Furthermore, if the loop body <em>does anything at all</em>,its running time must be <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59781" SRC="img451.gif" >.Hence, the loop body will dominate the calculation of the maximum,and the running time of the loop is simply <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59783" SRC="img452.gif" >.<P>If we don't know the exact number of iterations executed, <I>I</I>(<I>n</I>),we can still use Rule <A HREF="page73.html#ruleiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> provided we have an upper bound,<I>I</I>(<I>n</I>)=<I>O</I>(<I>f</I>(<I>n</I>)), on the number of iterations executed.In this case, the running time is <IMG WIDTH=229 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline59789" SRC="img453.gif" >.<P><P><A NAME="ruleiv"> </A> <IMG WIDTH=577 HEIGHT=174 ALIGN=BOTTOM ALT="ruledef1988" SRC="img454.gif" ><P><P>Rule <A HREF="page73.html#ruleiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> follows directly from the observationthat the total running time for an if-then-else statementwill never exceed the sum of the running time of the conditional test, <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif" >, plus the larger of the running times of the <em>then part</em>, <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif" >,and the <em>else part</em>, <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59803" SRC="img456.gif" >.<P><HR><A NAME="tex2html2050" HREF="page74.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2048" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2042" HREF="page72.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2052" 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 + -
显示快捷键?