📄 page60.html
字号:
<HTML><HEAD><TITLE>A Simple Example</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="tex2html1903" HREF="page61.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1901" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1895" HREF="page59.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1905" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003110000000000000000">A Simple Example</A></H2><A NAME="secasymptoticexample"> </A><P>Consider the function <I>f</I>(<I>n</I>)=8<I>n</I>+128 shown in Figure <A HREF="page60.html#figbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Clearly, <I>f</I>(<I>n</I>) is non-negative for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >.We wish to show that <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif" >.According to Definition <A HREF="page59.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,in order to show this we need to find an integer <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > and a constant <I>c</I><I>></I>0such that for all integers <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif" >, <IMG WIDTH=74 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58543" SRC="img242.gif" >.<P>It does not matter what the particular constants are--as long as they exist!For example, suppose we choose <I>c</I>=1.Then<P> <IMG WIDTH=500 HEIGHT=66 ALIGN=BOTTOM ALT="eqnarray1391" SRC="img243.gif" ><P>Since (<I>n</I>+8)<I>></I>0 for all values of <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >,we conclude that <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58551" SRC="img244.gif" >.That is, <IMG WIDTH=54 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58553" SRC="img245.gif" >.<P>So, we have that for <I>c</I>=1 and <IMG WIDTH=54 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58553" SRC="img245.gif" >, <IMG WIDTH=74 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58543" SRC="img242.gif" >for all integers <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif" >.Hence, <IMG WIDTH=93 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58535" SRC="img241.gif" >.Figure <A HREF="page60.html#figbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> clearly showsthat the function <IMG WIDTH=67 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58565" SRC="img246.gif" > is greater thanthe function <I>f</I>(<I>n</I>)=8<I>n</I>+128 to the right of <I>n</I>=16.<P>Of course, there are many other values of <I>c</I> and <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" > that will do.For example, <I>c</I>=2and <IMG WIDTH=152 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline58577" SRC="img247.gif" > will do,as will <I>c</I>=4 and <IMG WIDTH=136 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline58581" SRC="img248.gif" >.(See Figure <A HREF="page60.html#figbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P><P><A NAME="1426"> </A><A NAME="figbigoh"> </A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure1397" SRC="img250.gif" ><BR><STRONG>Figure:</STRONG> Showing that <IMG WIDTH=175 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58613" SRC="img249.gif" >.<BR><P><HR><A NAME="tex2html1903" HREF="page61.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1901" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1895" HREF="page59.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1905" 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 + -