?? page44.html
字號:
<HTML>
<HEAD>
<TITLE>About Harmonic Numbers</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html2435" HREF="page45.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page45.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2433" HREF="page35.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page35.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2427" HREF="page43.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page43.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2437" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2438" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION003180000000000000000">About Harmonic Numbers</A></H2>
<A NAME="secmodelharmonic"> </A>
<P>
The series <IMG WIDTH=84 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58459" SRC="img95.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img95.gif" > is
called the <em>harmonic series</em><A NAME=584> </A>,
and the summation
<P> <IMG WIDTH=289 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath58455" SRC="img96.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img96.gif" ><P>
gives rise to the series of <em>harmonic numbers</em><A NAME=590> </A>,
<IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline58461" SRC="img97.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img97.gif" >, <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline58463" SRC="img98.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/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 and
the difference between consecutive harmonic numbers
gets arbitrarily small ( <IMG WIDTH=111 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58467" SRC="img99.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img99.gif" >),
<em>the series does not converge</em>!
I.e., <IMG WIDTH=78 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline58469" SRC="img100.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img100.gif" > does not exist.
In other words, the summation <IMG WIDTH=49 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58471" SRC="img101.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img101.gif" >
goes off to infinity, but just barely.
<P>
Figure <A HREF="page44.html#figeuler" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page44.html#figeuler"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> helps us
to 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 represents
the function <IMG WIDTH=67 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58475" SRC="img102.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img102.gif" >.<A NAME="tex2html25" HREF="footnode.html#635" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#635"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A>
I.e., for <IMG WIDTH=102 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58493" SRC="img107.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img107.gif" >, <I>y</I>=1/<I>i</I>, for <IMG WIDTH=75 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58497" SRC="img108.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img108.gif" >
<P>
<P><A NAME="685"> </A><A NAME="figeuler"> </A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure605" SRC="img109.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img109.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=67 ALIGN=BOTTOM ALT="eqnarray688" SRC="img110.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img110.gif" ><P>
Thus, if we can determine the area under the descending staircase
in Figure <A HREF="page44.html#figeuler" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page44.html#figeuler"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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="eqnarray700" SRC="img111.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img111.gif" ><P>
<P>
Thus, <IMG WIDTH=37 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline58533" SRC="img112.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img112.gif" > is approximately <IMG WIDTH=26 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline58535" SRC="img113.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img113.gif" > for <I>n</I><I>></I>1.
<P>
If we approximate <IMG WIDTH=37 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline58533" SRC="img112.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img112.gif" > by <IMG WIDTH=26 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline58535" SRC="img113.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img113.gif" >,
the error in this approximation is equal to the area between the two curves.
In fact, the area between these two curves
is such an important quantity that it has its own symbol,
<IMG WIDTH=8 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline58543" SRC="img114.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img114.gif" ><A NAME=1138> </A>,
which is called <em>Euler's constant</em><A NAME=712> </A>.
The following derivation indicates a way
in which to compute Euler's constant:
<P> <IMG WIDTH=500 HEIGHT=199 ALIGN=BOTTOM ALT="eqnarray713" SRC="img115.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img115.gif" ><P>
<P>
A program to compute Euler's constant on the basis of this derivation
is given in Program <A HREF="page44.html#proggammac" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page44.html#proggammac"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
While this is not necessarily the most accurate
or most speedy way to compute Euler's constant,
it does give the correct result to six significant digits.
<P>
<P><A NAME="744"> </A><A NAME="proggammac"> </A> <IMG WIDTH=575 HEIGHT=218 ALIGN=BOTTOM ALT="program741" SRC="img116.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img116.gif" ><BR>
<STRONG>Program:</STRONG> Program to compute <IMG WIDTH=8 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline58543" SRC="img114.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img114.gif" ><BR>
<P>
<P>
So, with Euler's constant in hand,
we can write down an expression for the <IMG WIDTH=61 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline58549" SRC="img117.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img117.gif" > harmonic number:
<P><A NAME="eqnmodelhn"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation748" SRC="img118.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img118.gif" ><P>
where <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58551" SRC="img119.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img119.gif" > is the error introduced by the fact that
<IMG WIDTH=8 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline58543" SRC="img114.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img114.gif" > is defined as the difference between the curves on the interval
<IMG WIDTH=52 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58555" SRC="img120.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img120.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 that
for large enough values of <I>n</I>, <IMG WIDTH=75 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58563" SRC="img121.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img121.gif" >.<A NAME="tex2html27" HREF="footnode.html#1140" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#1140"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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="page44.html#eqnmodelhn" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page44.html#eqnmodelhn"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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="displaymath58456" SRC="img123.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img123.gif" ><P>
<P>
We now return to the question of finding the average running
time of Program <A HREF="page42.html#progfindmaxc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page42.html#progfindmaxc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
which finds the largest element of an array.
We can now rewrite Equation <A HREF="page43.html#eqnmodeltn" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page43.html#eqnmodeltn"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> to give
<P> <IMG WIDTH=500 HEIGHT=63 ALIGN=BOTTOM ALT="eqnarray758" SRC="img124.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img124.gif" ><P><HR><A NAME="tex2html2435" HREF="page45.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page45.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2433" HREF="page35.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page35.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2427" HREF="page43.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page43.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2437" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2438" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -