📄 page64.html
字号:
<HTML>
<HEAD>
<TITLE>More Big Oh Fallacies and Pitfalls</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html2689" HREF="page65.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page65.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2687" HREF="page57.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2681" HREF="page63.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page63.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2691" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2692" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION004170000000000000000">More Big Oh Fallacies and Pitfalls</A></H2>
<P>
The purpose of this section is
to dispel some common misconceptions about big oh.
The next fallacy is related to the selection
of the constants <I>c</I> and <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59043" SRC="img238.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img238.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=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59693" SRC="img373.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img373.gif" >, and <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif" >,
such that <IMG WIDTH=143 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59697" SRC="img374.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img374.gif" >.
Since <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59699" SRC="img375.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img375.gif" > for all integers <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif" > if <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59703" SRC="img376.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img376.gif" >,
then by Definition <A HREF="page57.html#defnbigoh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59705" SRC="img377.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img377.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_inline59707" SRC="img378.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img378.gif" >.
Let <IMG WIDTH=61 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59709" SRC="img379.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img379.gif" > and <IMG WIDTH=45 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59539" SRC="img348.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img348.gif" >.
Then <I>f</I>(<I>n</I>) must be <I>O</I>(<I>n</I>),
since <IMG WIDTH=138 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59717" SRC="img380.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img380.gif" >.
However, this line of reasoning is false because
according to Definition <A HREF="page57.html#defnbigoh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 the
notion 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_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" >, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif" >, <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59693" SRC="img373.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img373.gif" >, and <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif" >,
such that <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59227" SRC="img265.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img265.gif" >, <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59229" SRC="img266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img266.gif" >,
and for all integers <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif" >, <IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59737" SRC="img381.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img381.gif" >,
then <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59739" SRC="img382.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img382.gif" >.
</BLOCKQUOTE>
<P>
This fallacy arises from the following line of reasoning.
Consider the function <IMG WIDTH=98 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59741" SRC="img383.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img383.gif" > and <IMG WIDTH=98 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59743" SRC="img384.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img384.gif" >.
Since <IMG WIDTH=54 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59745" SRC="img385.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img385.gif" > for all values of <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59533" SRC="img344.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img344.gif" >,
we might be tempted to conclude that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59749" SRC="img386.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img386.gif" >.
In fact, such a conclusion is erroneous.
E.g., consider <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59175" SRC="img259.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img259.gif" > and <IMG WIDTH=101 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59753" SRC="img387.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img387.gif" >.
Clearly, the former is <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.gif" > and the latter is <IMG WIDTH=39 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59491" SRC="img332.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img332.gif" >.
Clearly too, <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59759" SRC="img388.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img388.gif" > for all values of <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif" >!
<P>
The previous fallacy essentially demonstrates that
while we may know how the asymptotic upper bounds on two functions
are 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 times
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -