📄 page64.html
字号:
<HTML><HEAD><TITLE>About Logarithms</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="tex2html1947" HREF="page65.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1945" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1939" HREF="page63.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1949" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003150000000000000000">About Logarithms</A></H2><P>In this section we determine the asymptotic behavior of logarithms.Interestingly,despite the fact that <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif" > diverges as <I>n</I> gets large, <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59019" SRC="img351.gif" > for all integers <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >. Hence, <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59023" SRC="img352.gif" >.Furthermore, as the following theorem will show, <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59015" SRC="img350.gif" > raised to any integer power <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" > is still <I>O</I>(<I>n</I>).<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremvii"> </A>For every integer <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" >, <IMG WIDTH=95 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59033" SRC="img354.gif" >.</BLOCKQUOTE><P> extbfProofThis result follows immediately from Theorem <A HREF="page62.html#theoremv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and the observation that for all integers <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" >,<P><A NAME="eqnloglimit"> </A> <IMG WIDTH=500 HEIGHT=37 ALIGN=BOTTOM ALT="equation1602" SRC="img355.gif" ><P>This observation can be proved by induction as follows:<P><b>Base Case</b>Consider the limit<P> <IMG WIDTH=289 HEIGHT=37 ALIGN=BOTTOM ALT="displaymath59011" SRC="img356.gif" ><P>for the case <I>k</I>=1.Using L'Hôpital's rule<A NAME="tex2html59" HREF="footnode.html#1758"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><A NAME=1623> </A>we see that<P> <IMG WIDTH=500 HEIGHT=51 ALIGN=BOTTOM ALT="eqnarray1624" SRC="img362.gif" ><P><P><b>Inductive Hypothesis</b>Assume that Equation <A HREF="page64.html#eqnloglimit"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> holds for <IMG WIDTH=101 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59057" SRC="img363.gif" >.Consider the case <I>k</I>=<I>m</I>+1.Using L'Hôpital's rule<A NAME=1636> </A> we see that<P> <IMG WIDTH=500 HEIGHT=95 ALIGN=BOTTOM ALT="eqnarray1637" SRC="img364.gif" ><P><P>Therefore, by induction on <I>m</I>, Equation <A HREF="page64.html#eqnloglimit"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>holds for all integers <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" >.<P>For example,using this property of logarithmstogether with the rule for determining the asymptotic behaviorof the product of two functions (Theorem <A HREF="page62.html#theoremiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>),we can determine that since <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59023" SRC="img352.gif" >,then <IMG WIDTH=107 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59067" SRC="img365.gif" >.<P><HR><A NAME="tex2html1947" HREF="page65.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1945" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1939" HREF="page63.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1949" 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 + -