page71.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 75 行
HTML
75 行
<HTML><HEAD><TITLE>More Notation-Theta and Little 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="tex2html2022" HREF="page72.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2020" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2014" HREF="page70.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2024" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION003300000000000000000">More Notation-Theta and Little Oh</A></H1><P>This section presents two less commonly used forms of asymptotic notation.They are:<UL><LI> A notation, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57625" SRC="img3.gif" >, to describe a function which is both <I>O</I>(<I>g</I>(<I>n</I>)) and <IMG WIDTH=52 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59549" SRC="img429.gif" >, for the same <I>g</I>(<I>n</I>). (Definition <A HREF="page71.html#defntheta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<LI> A notation, <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57627" SRC="img4.gif" >, to describe a function which is <I>O</I>(<I>g</I>(<I>n</I>)) but not <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59557" SRC="img430.gif" >, for the same <I>g</I>(<I>n</I>). (Definition <A HREF="page71.html#defnlittleoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).</UL><P><BLOCKQUOTE> <b>Definition (Theta)</b><A NAME=1888> </A><A NAME=2243> </A><A NAME="defntheta"> </A>Consider a function <I>f</I>(<I>n</I>) which is non-negativefor all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >.We say that ``<I>f</I>(<I>n</I>) is theta <I>g</I>(<I>n</I>),''which we write <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59571" SRC="img432.gif" >,if and only if<I>f</I>(<I>n</I>) is <I>O</I>(<I>g</I>(<I>n</I>)) <em>and</em> <I>f</I>(<I>n</I>) is <IMG WIDTH=52 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59549" SRC="img429.gif" >.</BLOCKQUOTE><P>Recall that we showed in Section <A HREF="page63.html#secasymptoticpolyi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> thata polynomial in <I>n</I>,say <IMG WIDTH=356 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59001" SRC="img348.gif" >,is <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58823" SRC="img308.gif" >.We also showed in Section <A HREF="page70.html#secasymptoticpolyii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> thata such a polynomial is <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59587" SRC="img433.gif" >.Therefore, according to Definition <A HREF="page71.html#defntheta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we will write <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59589" SRC="img434.gif" >.<P><BLOCKQUOTE> <b>Definition (Little Oh)</b><A NAME=1900> </A><A NAME=2244> </A><A NAME="defnlittleoh"> </A>Consider a function <I>f</I>(<I>n</I>) which is non-negativefor all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >.We say that ``<I>f</I>(<I>n</I>) is little oh <I>g</I>(<I>n</I>),''which we write <I>f</I>(<I>n</I>)=<I>o</I>(<I>g</I>(<I>n</I>)),if and only if<I>f</I>(<I>n</I>) is <I>O</I>(<I>g</I>(<I>n</I>)) but <I>f</I>(<I>n</I>) is <em>not</em> <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59557" SRC="img430.gif" >.</BLOCKQUOTE><P>Little oh notation represents a kind of<em>loose asymptotic bound</em><A NAME=1906> </A>in the sense that if we are given that <I>f</I>(<I>n</I>)=<I>o</I>(<I>g</I>(<I>n</I>)),then we know that <I>g</I>(<I>n</I>) is an asymptotic upper boundsince <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)),but <I>g</I>(<I>n</I>) is <em>not</em> an asymptotic lower boundsince <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)) and <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59621" SRC="img435.gif" >implies that <IMG WIDTH=104 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59623" SRC="img436.gif" >.<A NAME="tex2html82" HREF="footnode.html#2245"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P>For example, consider the function <I>f</I>(<I>n</I>)=<I>n</I>+1.Clearly, <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif" >.Clearly too, <IMG WIDTH=92 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59629" SRC="img437.gif" >,since not matter what <I>c</I> we choose,for large enough <I>n</I>, <IMG WIDTH=81 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59635" SRC="img438.gif" >.Thus, we may write <IMG WIDTH=146 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59637" SRC="img439.gif" >.<P><HR><A NAME="tex2html2022" HREF="page72.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2020" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2014" HREF="page70.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2024" 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 + =
减小字号Ctrl + -
显示快捷键?