page46.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 102 行
HTML
102 行
<HTML><HEAD><TITLE>About Harmonic Numbers</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="tex2html1735" HREF="page47.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1733" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1727" HREF="page45.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1737" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION002180000000000000000">About Harmonic Numbers</A></H2><A NAME="secmodelharmonic"> </A><P>The series <IMG WIDTH=83 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline57919" SRC="img95.gif" > iscalled the <em>harmonic series</em><A NAME=611> </A>,and the summation<P> <IMG WIDTH=289 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath57915" SRC="img96.gif" ><P>gives rise to the series of <em>harmonic numbers</em><A NAME=617> </A>, <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57921" SRC="img97.gif" >, <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57923" SRC="img98.gif" >, ....As it turns out,harmonic numbers often creep into the analysis of algorithms.Therefore, we should understand a little bit about how they behave.<P>A remarkable characteristic of harmonic numbers is that,even though as <I>n</I> gets large andthe difference between consecutive harmonic numbersgets arbitrarily small ( <IMG WIDTH=111 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline57927" SRC="img99.gif" >),<em>the series does not converge</em>!That is, <IMG WIDTH=80 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline57929" SRC="img100.gif" > does not exist.In other words, the summation <IMG WIDTH=49 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline57931" SRC="img101.gif" >goes off to infinity, but just barely.<P>Figure <A HREF="page46.html#figeuler"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> helps usto understand the behavior of harmonic numbers.The smooth curve in this figure is the function <I>y</I>=1/<I>x</I>.The descending staircase representsthe function <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57935" SRC="img102.gif" >.<A NAME="tex2html28" HREF="footnode.html#666"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P><P><A NAME="732"> </A><A NAME="figeuler"> </A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure632" SRC="img107.gif" ><BR><STRONG>Figure:</STRONG> Computing harmonic numbers.<BR><P><P>Notice that the area under the staircase between 1 and <I>n</I>for any integer <I>n</I><I>></I>1 is given by<P> <IMG WIDTH=500 HEIGHT=68 ALIGN=BOTTOM ALT="eqnarray735" SRC="img108.gif" ><P>Thus, if we can determine the area under the descending staircasein Figure <A HREF="page46.html#figeuler"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we can determine the values of the harmonic numbers.<P>As an approximation,consider the area under the smooth curve <I>y</I>=1/<I>x</I>:<P> <IMG WIDTH=500 HEIGHT=59 ALIGN=BOTTOM ALT="eqnarray747" SRC="img109.gif" ><P><P>Thus, <IMG WIDTH=36 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline57987" SRC="img110.gif" > is approximately <IMG WIDTH=25 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline57989" SRC="img111.gif" > for <I>n</I><I>></I>1.<P>If we approximate <IMG WIDTH=36 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline57987" SRC="img110.gif" > by <IMG WIDTH=25 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline57989" SRC="img111.gif" >,the error in this approximation is equal to the area between the two curves.In fact, the area between these two curvesis such an important quantity that it has its own symbol, <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline57997" SRC="img112.gif" ><A NAME=1197> </A>,which is called <em>Euler's constant</em><A NAME=759> </A>.The following derivation indicates a wayin which to compute Euler's constant:<P> <IMG WIDTH=500 HEIGHT=200 ALIGN=BOTTOM ALT="eqnarray760" SRC="img113.gif" ><P><P>A program to compute Euler's constant on the basis of this derivationis given in Program <A HREF="page46.html#progexamplee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.While this is not necessarily the most accurateor most speedy way to compute Euler's constant,it does give the correct result to six significant digits.<P><P><A NAME="792"> </A><A NAME="progexamplee"> </A> <IMG WIDTH=575 HEIGHT=142 ALIGN=BOTTOM ALT="program789" SRC="img114.gif" ><BR><STRONG>Program:</STRONG> Program to compute <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline57997" SRC="img112.gif" >.<BR><P><P>So, with Euler's constant in hand,we can write down an expression for the <IMG WIDTH=60 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58003" SRC="img115.gif" > harmonic number:<P><A NAME="eqnmodelhn"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation797" SRC="img116.gif" ><P>where <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58005" SRC="img117.gif" > is the error introduced by the fact that <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline57997" SRC="img112.gif" > is defined as the difference between the curves on the interval <IMG WIDTH=52 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58009" SRC="img118.gif" >, but we only need the difference on the interval [1,<I>n</I>].As it turns out, it can be shown (but not here),that there exists a constant <I>K</I> such thatfor large enough values of <I>n</I>, <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58017" SRC="img119.gif" >.<A NAME="tex2html30" HREF="footnode.html#1200"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P>Since the error term is less than 1/<I>n</I>,we can add 1/<I>n</I> to both sides of Equation <A HREF="page46.html#eqnmodelhn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and still have an error which goes to zero as <I>n</I> gets large.Thus, the usual approximation for the harmonic number is<P> <IMG WIDTH=300 HEIGHT=15 ALIGN=BOTTOM ALT="displaymath57916" SRC="img121.gif" ><P><P>We now return to the question of finding the average runningtime of Program <A HREF="page44.html#progexampled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,which finds the largest element of an array.We can now rewrite Equation <A HREF="page45.html#eqnmodeltn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to give<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray807" SRC="img122.gif" ><P><HR><A NAME="tex2html1735" HREF="page47.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1733" HREF="page37.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1727" HREF="page45.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1737" 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 + =
减小字号Ctrl + -
显示快捷键?