📄 page62.html
字号:
<HTML><HEAD><TITLE>Properties of Big Oh</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="tex2html1925" HREF="page63.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1923" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1917" HREF="page61.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1927" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003130000000000000000">Properties of Big Oh</A></H2><P>In this section we examine some of the mathematical properties of big oh.In particular, suppose we know that <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif" > and <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58679" SRC="img263.gif" >.<UL><LI> What can we say about the asymptotic behavior of the <em>sum</em> of <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" >? (Theorems <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page62.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<LI> What can we say about the asymptotic behavior of the <em>product</em> of <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" >? (Theorems <A HREF="page62.html#theoremiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page62.html#theoremiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<LI> How are <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif" > related when <IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58693" SRC="img267.gif" >? (Theorem <A HREF="page62.html#theoremv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).</UL><P>The first theorem addresses the asymptotic behavior of the sumof two functions whose asymptotic behaviors are known:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremi"> </A>If <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif" > and <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58679" SRC="img263.gif" >,then<P> <IMG WIDTH=382 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath58665" SRC="img268.gif" ><P></BLOCKQUOTE><P> extbfProofBy Definition <A HREF="page59.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, there exist two integers, <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58699" SRC="img269.gif" > and <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58701" SRC="img270.gif" >and two constants <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58703" SRC="img271.gif" > and <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58705" SRC="img272.gif" > such that <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58707" SRC="img273.gif" > for <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58709" SRC="img274.gif" > and <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58711" SRC="img275.gif" > for <IMG WIDTH=46 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58713" SRC="img276.gif" >.<P>Let <IMG WIDTH=120 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58715" SRC="img277.gif" > and <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58717" SRC="img278.gif" >.Consider the sum <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58719" SRC="img279.gif" > for <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif" >:<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray1463" SRC="img280.gif" ><P>Thus, <IMG WIDTH=260 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58723" SRC="img281.gif" >.<P>According to Theorem <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,if we know that functions <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" > are <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif" > and <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58731" SRC="img283.gif" >, respectively,the <em>sum</em> <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58719" SRC="img279.gif" > is <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58735" SRC="img284.gif" >.The meaning of <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58737" SRC="img285.gif" > is this context isthe <em>function</em> <I>h</I>(<I>n</I>) where <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58741" SRC="img286.gif" >for integers all <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >.<P>For example, consider the functions <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58745" SRC="img287.gif" > and <IMG WIDTH=143 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58747" SRC="img288.gif" >.Then<P> <IMG WIDTH=500 HEIGHT=94 ALIGN=BOTTOM ALT="eqnarray1468" SRC="img289.gif" ><P><P>Theorem <A HREF="page62.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> helps us simplify the asymptotic analysisof the sum of functions by allowing us to drop the <IMG WIDTH=29 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline58753" SRC="img290.gif" >required by Theorem <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> in certain circumstances:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremii"> </A>If <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58755" SRC="img291.gif" >in which <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" > are both non-negative for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >such that <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58763" SRC="img292.gif" >for some limit <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58765" SRC="img293.gif" >,then <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58767" SRC="img294.gif" >.</BLOCKQUOTE><P> extbfProofAccording to the definition of limits<A NAME=1482> </A>, the notation<P> <IMG WIDTH=304 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath58666" SRC="img295.gif" ><P>means that, given any arbitrary positive value <IMG WIDTH=6 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline58769" SRC="img296.gif" >,it is possible to find a value <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" >such that for all <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif" ><P> <IMG WIDTH=305 HEIGHT=40 ALIGN=BOTTOM ALT="displaymath58667" SRC="img297.gif" ><P><P>Thus, if we chose a particular value, say <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58775" SRC="img298.gif" >,then there exists a corresponding <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > such that<P> <IMG WIDTH=500 HEIGHT=105 ALIGN=BOTTOM ALT="eqnarray1488" SRC="img299.gif" ><P><P>Consider the sum <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58755" SRC="img291.gif" >:<P> <IMG WIDTH=500 HEIGHT=88 ALIGN=BOTTOM ALT="eqnarray1494" SRC="img300.gif" ><P>where <IMG WIDTH=138 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58781" SRC="img301.gif" >.Thus, <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58767" SRC="img294.gif" >.<P>Consider a pair of functions <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" >,which are known to be <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif" > and <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58731" SRC="img283.gif" >, respectively.According to Theorem <A HREF="page62.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the sum <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58755" SRC="img291.gif" > is <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58735" SRC="img284.gif" >.However, Theorem <A HREF="page62.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> says that,if <IMG WIDTH=139 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58797" SRC="img302.gif" > exists,then the sum <I>f</I>(<I>n</I>) is simply <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58801" SRC="img303.gif" > which,by the transitive property (see Theorem <A HREF="page62.html#theoremv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> below), is <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif" >.<P>In other words, if the ratio <IMG WIDTH=80 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58805" SRC="img304.gif" >asymptotically approaches a constant as <I>n</I> gets large,we can say that <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58719" SRC="img279.gif" > is <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif" >,which is often a lot simpler than <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58735" SRC="img284.gif" >.<P>Theorem <A HREF="page62.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is particularly useful result.Consider <IMG WIDTH=73 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58815" SRC="img305.gif" > and <IMG WIDTH=73 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58627" SRC="img257.gif" >.<P> <IMG WIDTH=500 HEIGHT=96 ALIGN=BOTTOM ALT="eqnarray1501" SRC="img306.gif" ><P>From this we can conclude that <IMG WIDTH=228 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58819" SRC="img307.gif" >.Thus, Theorem <A HREF="page62.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> suggests thatthe sum of a series of powers of <I>n</I> is <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58823" SRC="img308.gif" >,where <I>m</I> is the largest power of <I>n</I> in the summation.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -