page65.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 68 行

HTML
68 行
字号 
<HTML><HEAD><TITLE>Tight Big Oh Bounds</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="tex2html1958" HREF="page66.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1956" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1950" HREF="page64.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1960" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003160000000000000000">Tight Big Oh Bounds</A></H2><P>Big oh notation characterizes the asymptotic behavior of a functionby providing an upper bound on the rate at which the function growsas <I>n</I> gets large.Unfortunately, the notation does not tell us how closethe actual behavior of the function is to the bound.That is, the bound might be very close (tight)or it might be overly conservative (loose).<P>The following definition tells us what makes a bound tight,and how we can test to see whether a given asymptotic boundis the best one available.<P><BLOCKQUOTE> <b>Definition (Tightness)</b><A NAME=1656>&#160;</A><A NAME="defntightness">&#160;</A>    Consider a function <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)).    If for every function <I>h</I>(<I>n</I>) such that <I>f</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>))    it is also true that <I>g</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)),    then we say that <I>g</I>(<I>n</I>) is a    <em>tight asymptotic bound</em><A NAME=1659>&#160;</A>    on <I>f</I>(<I>n</I>).</BLOCKQUOTE><P>For example, consider the function <I>f</I>(<I>n</I>)=8<I>n</I>+128.In Section&nbsp;<A HREF="page60.html#secasymptoticexample"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,it was shown that  <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif"  >.However, since <I>f</I>(<I>n</I>) is a polynomial in <I>n</I>,Theorem&nbsp;<A HREF="page63.html#theoremvi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> tells us that <I>f</I>(<I>n</I>)=<I>O</I>(<I>n</I>).Clearly <I>O</I>(<I>n</I>) is a tighter bound on the asymptotic behavior of <I>f</I>(<I>n</I>)than is  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  >.<P>By Definition&nbsp;<A HREF="page65.html#defntightness"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,in order to show that <I>g</I>(<I>n</I>)=<I>n</I> is a tight bound on <I>f</I>(<I>n</I>),we need to show that for every function <I>h</I>(<I>n</I>)such that <I>f</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)), it is also true that <I>g</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)).<P>We will show this result using proof by contradiction:Assume that <I>g</I>(<I>n</I>) is <em>not</em> a tight bound for <I>f</I>(<I>n</I>)=8<I>n</I>+128.Then there exists a function <I>h</I>(<I>n</I>)such that <I>f</I>(<I>n</I>)=8<I>n</I>+128=<I>O</I>(<I>h</I>(<I>n</I>)),but for which  <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59117" SRC="img366.gif"  >.Since 8<I>n</I>+128=<I>O</I>(<I>h</I>(<I>n</I>)), by the definition of big oh there existpositive constants <I>c</I> and  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  > such that <IMG WIDTH=119 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59125" SRC="img367.gif"  > for all  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >.<P>Clearly, for all  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >,  <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59131" SRC="img368.gif"  >.Therefore,  <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59133" SRC="img369.gif"  >.But then, by the definition of big oh,we have that <I>g</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>))--a contradiction!Therefore, the bound <I>f</I>(<I>n</I>)=<I>O</I>(<I>n</I>) is a tight bound.<P><HR><A NAME="tex2html1958" HREF="page66.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1956" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1950" HREF="page64.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1960" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page65.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page65.html 源码文件，采用 HTML 编程语言编写，共 68 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?