page307.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 55 行
HTML
55 行
<HTML><HEAD><TITLE>Solving The Recurrence-Telescoping</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="tex2html4739" HREF="page308.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4737" HREF="page305.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4731" HREF="page306.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4741" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010320000000000000000">Solving The Recurrence-Telescoping</A></H2><P>This section presents a technique for solving recurrence relationssuch as Equation <A HREF="page306.html#eqnsrchtreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>called <em>telescoping</em><A NAME=18453> </A>.The basic idea is this:We rewrite the recurrence formula so that a similar functionalform appears on both sides of the equal sign.For example, in this case, we consider <I>n</I><I>></I>2 and divideboth sides of Equation <A HREF="page306.html#eqnsrchtreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by <I>n</I>+1 to get<P> <IMG WIDTH=369 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath63981" SRC="img1209.gif" ><P>Since this equation is valid for any <I>n</I><I>></I>2,we can write the following series of equations:<P><A NAME="eqnsrchtreef"> </A><A NAME="eqnsrchtreee"> </A> <IMG WIDTH=537 HEIGHT=271 ALIGN=BOTTOM ALT="eqnarray18463" SRC="img1210.gif" ><P>Each subsequent equation in this series is obtained by substituting <I>n</I>-1for <I>n</I> in the preceding equation.In principle, we repeat this substitution until we get an expressionon the right-hand-side involving the base case.In this example, we stop at <I>n</I>-<I>k</I>-1=2.<P>Because Equation <A HREF="page307.html#eqnsrchtreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> has a similar functional form on bothsides of the equal sign,when we add Equation <A HREF="page307.html#eqnsrchtreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> through Equation <A HREF="page307.html#eqnsrchtreef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> together, most of the terms cancel leaving<P> <IMG WIDTH=500 HEIGHT=121 ALIGN=BOTTOM ALT="eqnarray18510" SRC="img1211.gif" ><P>where <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63995" SRC="img1212.gif" > is the <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" ><em>harmonic number</em><A NAME=18534> </A>.In Section <A HREF="page46.html#secmodelharmonic"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> it is shown that <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63999" SRC="img1213.gif" >,where <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64001" SRC="img1214.gif" >is called <em>Euler's constant</em><A NAME=18537> </A>.Thus, we get that the average internal path length of the averagebinary search tree with <I>n</I> internal nodes is<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray18538" SRC="img1215.gif" ><P><P>Finally, we get to the point:The average depth of a node in the average binary search tree with <I>n</I>nodes is<P> <IMG WIDTH=500 HEIGHT=130 ALIGN=BOTTOM ALT="eqnarray18540" SRC="img1216.gif" ><P><HR><A NAME="tex2html4739" HREF="page308.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4737" HREF="page305.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4731" HREF="page306.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4741" 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 + -
显示快捷键?