📄 page70.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>About Polynomials Again</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="tex2html2011" HREF="page71.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2009" HREF="page68.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2005" HREF="page69.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2013" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003220000000000000000">About Polynomials Again</A></H2><A NAME="secasymptoticpolyii">&#160;</A><P>In this section we reexamine the asymptotic behavior of polynomials in <I>n</I>.In Section&nbsp;<A HREF="page63.html#secasymptoticpolyi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we showed that  <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58969" SRC="img336.gif"  >.That is, <I>f</I>(<I>n</I>) grows asymptotically no more quickly than  <IMG WIDTH=21 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline59477" SRC="img415.gif"  >.This time we are interested in the asymptotic lower boundrather than the asymptotic upper bound.We will see that as <I>n</I> gets large,the term involving  <IMG WIDTH=21 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline59477" SRC="img415.gif"  > also dominates the lower boundin the sense that <I>f</I>(<I>n</I>) grows asymptotically <em>as quickly</em> as  <IMG WIDTH=21 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline59477" SRC="img415.gif"  >.That is, that  <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59487" SRC="img416.gif"  >.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremviii">&#160;</A>Consider a polynomial<A NAME=1801>&#160;</A> in <I>n</I> of the form<P> <IMG WIDTH=500 HEIGHT=68 ALIGN=BOTTOM ALT="eqnarray1556" SRC="img334.gif"  ><P>where  <IMG WIDTH=50 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58967" SRC="img335.gif"  >.Then  <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59487" SRC="img416.gif"  >.</BLOCKQUOTE><P>	extbfProofWe begin by taking the term  <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59495" SRC="img417.gif"  > out of the summation:<P> <IMG WIDTH=500 HEIGHT=99 ALIGN=BOTTOM ALT="eqnarray1810" SRC="img418.gif"  ><P><P>Since, <I>n</I> is a non-negative integer and  <IMG WIDTH=50 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58967" SRC="img335.gif"  >,the term  <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59495" SRC="img417.gif"  > is positive.For each of the remaining terms in the summation,  <IMG WIDTH=99 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59503" SRC="img419.gif"  >.Hence<P> <IMG WIDTH=500 HEIGHT=157 ALIGN=BOTTOM ALT="eqnarray1816" SRC="img420.gif"  ><P><P>Note that for integers  <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58983" SRC="img341.gif"  >, <IMG WIDTH=118 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59507" SRC="img421.gif"  > for  <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59509" SRC="img422.gif"  >.Thus<P> <IMG WIDTH=500 HEIGHT=103 ALIGN=BOTTOM ALT="eqnarray1830" SRC="img423.gif"  ><P><P>Consider the term in parentheses on the right.What we need to do is to find a positive constant <I>c</I>and an integer  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  >so that for all integers  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >this term is greater than or equal to <I>c</I>:<P> <IMG WIDTH=372 HEIGHT=46 ALIGN=BOTTOM ALT="displaymath59469" SRC="img424.gif"  ><P><P>We choose the value  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  > for which the term is greater than zero:<P> <IMG WIDTH=500 HEIGHT=102 ALIGN=BOTTOM ALT="eqnarray1847" SRC="img425.gif"  ><P>The value <IMG WIDTH=175 HEIGHT=38 ALIGN=MIDDLE ALT="tex2html_wrap_inline59521" SRC="img426.gif"  >will suffice!Thus<P><A NAME="eqnomegapoly">&#160;</A> <IMG WIDTH=500 HEIGHT=130 ALIGN=BOTTOM ALT="eqnarray1861" SRC="img427.gif"  ><P><P>From Equation&nbsp;<A HREF="page70.html#eqnomegapoly"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we see thatwe have found the constants  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  > and <I>c</I>,such that for all  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >,  <IMG WIDTH=177 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59529" SRC="img428.gif"  >.Thus,  <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59487" SRC="img416.gif"  >.<P>This property of the asymptotic behavior of polynomialsis used extensively.In fact, whenever we have a function,which is a polynomial in <I>n</I>, <IMG WIDTH=356 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59001" SRC="img348.gif"  >we will immediately ``drop'' the less significant terms(i.e., terms involving powers of <I>n</I> which are less than <I>m</I>),as well as the leading coefficient,  <IMG WIDTH=20 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline59007" SRC="img349.gif"  >,to write  <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59487" SRC="img416.gif"  >.<P><HR><A NAME="tex2html2011" HREF="page71.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2009" HREF="page68.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2005" HREF="page69.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2013" 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 + -