📄 page66.html
字号:
<HTML><HEAD><TITLE>More Big Oh Fallacies and Pitfalls</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="tex2html1969" HREF="page67.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1967" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1961" HREF="page65.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1971" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003170000000000000000">More Big Oh Fallacies and Pitfalls</A></H2><P>The purpose of this section isto dispel some common misconceptions about big oh.The next fallacy is related to the selectionof the constants <I>c</I> and <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > used to show a big oh relation.<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyiii"> </A> Consider non-negative functions <I>f</I>(<I>n</I>), <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59145" SRC="img370.gif" >, and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif" >, such that <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59149" SRC="img371.gif" >. Since <IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59151" SRC="img372.gif" > for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" > if <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59155" SRC="img373.gif" >, then by Definition <A HREF="page59.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59157" SRC="img374.gif" >.</BLOCKQUOTE><P>This fallacy often results from the following line of reasoning:Consider the function <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59159" SRC="img375.gif" >.Let <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59161" SRC="img376.gif" > and <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58989" SRC="img345.gif" >.Then <I>f</I>(<I>n</I>) must be <I>O</I>(<I>n</I>),since <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59169" SRC="img377.gif" > for all <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif" >.However, this line of reasoning is false becauseaccording to Definition <A HREF="page59.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,<I>c</I> must be a <em>positive constant</em>, not a function of <I>n</I>.<P>The next fallacy involves a misunderstanding of thenotion of the <em>asymptotic upper bound</em>.<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyiv"> </A> Given non-negative functions <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" >, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" >, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59145" SRC="img370.gif" >, and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif" >, such that <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif" >, <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58679" SRC="img263.gif" >, and for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >, <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59191" SRC="img378.gif" >, then <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59193" SRC="img379.gif" >.</BLOCKQUOTE><P>This fallacy arises from the following line of reasoning.Consider the function <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59195" SRC="img380.gif" > and <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59197" SRC="img381.gif" >.Since <IMG WIDTH=54 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59199" SRC="img382.gif" > for all values of <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif" >,we might be tempted to conclude that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59203" SRC="img383.gif" >.In fact, such a conclusion is erroneous.For example, consider <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58625" SRC="img256.gif" > and <IMG WIDTH=100 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59207" SRC="img384.gif" >.Clearly, the former is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > and the latter is <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" >.Clearly too, <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59213" SRC="img385.gif" > for all values of <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >!<P>The previous fallacy essentially demonstrates thatwhile we may know how the asymptotic upper bounds on two functionsare related, we don't necessarily know, in general,the relative behavior of the two bounded functions.<P>This fallacy often arises in the comparison of the performance of algorithms.Suppose we are comparing two algorithms, <I>A</I> and <I>B</I>,to solve a given problem and we have determined that the running timesof these algorithms are <IMG WIDTH=123 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59221" SRC="img386.gif" > and <IMG WIDTH=124 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59223" SRC="img387.gif" >,respectively.Fallacy <A HREF="page66.html#fallacyiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> demonstrates that it is an error to concludefrom the fact that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59225" SRC="img388.gif" > for all <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >that algorithm <I>A</I> willsolve the problem faster than algorithm <I>B</I> for all problem sizes.<P>But what about any one specific problem size?Can we conclude that for a given problem size, say <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" >,that algorithm <I>A</I> is faster than algorithm <I>B</I>?The next fallacy addresses this issue.<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyv"> </A> Given non-negative functions <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif" >, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif" >, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59145" SRC="img370.gif" >, and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif" >, such that <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif" >, <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58679" SRC="img263.gif" >, and for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >, <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59191" SRC="img378.gif" >, there exists an integer <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > for which then <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59257" SRC="img389.gif" >.</BLOCKQUOTE><P>This fallacy arises from a similar line of reasoning as the preceding one.Consider the function <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59195" SRC="img380.gif" > and <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59197" SRC="img381.gif" >.Since <IMG WIDTH=54 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59199" SRC="img382.gif" > for all values of <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif" >,we might be tempted to conclude that there existsa value <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > for which <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59269" SRC="img390.gif" >.Such a conclusion is erroneous.For example, consider <IMG WIDTH=73 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59271" SRC="img391.gif" > and <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59273" SRC="img392.gif" >.Clearly, the former is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > and the latter is <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" >.Clearly too, since <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59213" SRC="img385.gif" > for all values of <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >,there does not exist any value <IMG WIDTH=46 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59283" SRC="img393.gif" >for which <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59269" SRC="img390.gif" >.<P>The final fallacy shows that not all functions are<em>commensurate</em><A NAME=1684> </A>:<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyvi"> </A> Given two non-negative functions <I>f</I>(<I>n</I>) and <I>g</I>(<I>n</I>) then either <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)) or <I>g</I>(<I>n</I>)=<I>O</I>(<I>f</I>(<I>n</I>)).</BLOCKQUOTE><P>This fallacy arises from thinking that the relation <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >is like <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59297" SRC="img394.gif" > and can be used to compare any two functions.However, not all functions are commensurate.<A NAME="tex2html66" HREF="footnode.html#1761"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>Consider the following functions:<P> <IMG WIDTH=500 HEIGHT=102 ALIGN=BOTTOM ALT="eqnarray1690" SRC="img395.gif" ><P>Clearly, there does not exist a constant <I>c</I>for which <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58527" SRC="img240.gif" > for any even integer <I>n</I>,since the <I>g</I>(<I>n</I>) is zero and <I>f</I>(<I>n</I>) is not.Conversely, there does not exist a constant <I>c</I>for which <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59319" SRC="img396.gif" > for any odd integer <I>n</I>,since the <I>f</I>(<I>n</I>) is zero and <I>g</I>(<I>n</I>) is not.Hence, neither <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)) nor <I>g</I>(<I>n</I>)=<I>O</I>(<I>f</I>(<I>n</I>)) is true.<P><HR><A NAME="tex2html1969" HREF="page67.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1967" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1961" HREF="page65.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1971" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -