📄 page61.html
字号:
<HTML><HEAD><TITLE>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="tex2html1914" HREF="page62.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1912" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1906" HREF="page60.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1916" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003120000000000000000">Big Oh Fallacies and Pitfalls</A></H2><P>Unfortunately, the way we write big oh notationcan be misleading to the naıve reader.This section presents two fallacies which arisebecause of a misinterpretation of the notation.<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyi"> </A>Given that <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58615" SRC="img251.gif" > and <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58617" SRC="img252.gif" >,then <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58619" SRC="img253.gif" >.</BLOCKQUOTE><P>Consider the equations:<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray1435" SRC="img254.gif" ><P>Clearly, it is reasonable to conclude that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58619" SRC="img253.gif" >.<P>However, consider these equations:<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray1437" SRC="img255.gif" ><P>It <em>does not</em> follow that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58619" SRC="img253.gif" >.For example, <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58625" SRC="img256.gif" > and <IMG WIDTH=73 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58627" SRC="img257.gif" > are both <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >, but they are not equal.<P><BLOCKQUOTE> <b>Fallacy</b><A NAME="fallacyii"> </A>If <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)),then <IMG WIDTH=124 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58633" SRC="img259.gif" >.</BLOCKQUOTE><P>Consider functions <I>f</I>, <I>g</I>, and <I>h</I>, such that <I>f</I>(<I>n</I>)=<I>h</I>(<I>g</I>(<I>n</I>)).It is reasonable to conclude that <IMG WIDTH=120 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58643" SRC="img260.gif" >provided that <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58645" SRC="img261.gif" > is an invertible function.However, while we may write <I>f</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)),the equation <IMG WIDTH=124 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58633" SRC="img259.gif" > is nonsensical and meaningless.Big oh is not a mathematical function,so it has no inverse!<P>The reason for these difficulties is thatwe should read the notation <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif" > as``<I>f</I>(<I>n</I>) is big oh <I>n</I> squared''not``<I>f</I>(<I>n</I>) equals big oh of <I>n</I> squared.''The equal sign in the expression does not really denote mathematical equality!And the use of the functional form, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >,does not really mean that <I>O</I> is a mathematical function!<P><HR><A NAME="tex2html1914" HREF="page62.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1912" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1906" HREF="page60.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1916" 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 + -