📄 page67.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>Conventions for Writing Big Oh Expressions</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="tex2html1978" HREF="page68.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1976" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1972" HREF="page66.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1980" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003180000000000000000">Conventions for Writing Big Oh Expressions</A></H2><P>Certain conventions have evolved which concernhow big oh expressions are normally written:<UL><LI>	First, it is common practice when writing big oh expressions	to drop all but the most significant terms.	Thus, instead of  <IMG WIDTH=133 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59331" SRC="img397.gif"  > we simply write  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  >.<LI>	Second, it is common practice to drop constant coefficients.	Thus, instead of  <IMG WIDTH=48 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59335" SRC="img398.gif"  >, we simply write  <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  >.	As a special case of this rule,	if the function is a constant,	instead of, say O(1024), we simply write <I>O</I>(1).</UL><P>Of course, in order for a particular big oh expression to bethe most useful, we prefer to find a <em>tight</em> asymptotic bound(see Definition&nbsp;<A HREF="page65.html#defntightness"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).For example, while it is not wrong to write  <IMG WIDTH=123 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59341" SRC="img399.gif"  >,we prefer to write <I>f</I>(<I>n</I>)=<I>O</I>(<I>n</I>), which is a tight bound.<P>Certain big oh expressions occur so frequently that they are given names.Table&nbsp;<A HREF="page67.html#tblbigohnames"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> lists some of the commonly occurringbig oh expressions and the usual name given to each of them.<P><P><A NAME="1707">&#160;</A><P>    <A NAME="tblbigohnames">&#160;</A>    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=LEFT><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>	    expression </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> name </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> constant<A NAME=1712>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> logarithmic<A NAME=1713>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=63 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59349" SRC="img401.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> log squared<A NAME=1714>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	    <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> linear<A NAME=1715>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>n</I> log <I>n</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> quadratic<A NAME=1716>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> cubic<A NAME=1717>&#160;</A> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 	     <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59363" SRC="img403.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> exponential<A NAME=1718>&#160;</A> </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> The names of common big oh expressions.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html1978" HREF="page68.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1976" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1972" HREF="page66.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1980" 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 + -