📄 page68.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>An Asymptotic Lower Bound-Omega</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="tex2html1989" HREF="page69.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1987" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1981" HREF="page67.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1991" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION003200000000000000000">An Asymptotic Lower Bound-Omega</A></H1><P>The big oh notation introduced in the preceding sectionis an asymptotic <em>upper bound</em>.In this section, we introduce a similar notationfor characterizing the asymptotic behavior of a function,but in this case it is a <em>lower bound</em>.<P><BLOCKQUOTE> <b>Definition (Omega)</b><A NAME=1727>&#160;</A><A NAME=1762>&#160;</A><A NAME="defnomega">&#160;</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 omega <I>g</I>(<I>n</I>),''which we write  <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59375" SRC="img405.gif"  >,if there exists an integer  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  > and a constant <I>c</I><I>&gt;</I>0such that for all integers  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >, <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59383" SRC="img406.gif"  >.</BLOCKQUOTE><P>The definition of omega is almost identical to that of big oh.The only difference is in the comparison--for big oh it is <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58527" SRC="img240.gif"  >; for omega, it is  <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59383" SRC="img406.gif"  >.All of the same conventions and caveats apply to omega as they do to big oh.<P><BR> <HR><UL> <LI> <A NAME="tex2html1992" HREF="page69.html#SECTION003210000000000000000">A Simple Example</A><LI> <A NAME="tex2html1993" HREF="page70.html#SECTION003220000000000000000">About Polynomials Again</A></UL><HR><A NAME="tex2html1989" HREF="page69.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1987" HREF="page58.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1981" HREF="page67.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1991" 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>
⌨️ 快捷键说明

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