📄 page73.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
📖 第 1 页 / 共 2 页
字号:
12 下一页
<HTML>
<HEAD>
<TITLE>Example-Fibonacci 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="tex2html2801" HREF="page74.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.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="tex2html2799" HREF="page70.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.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="tex2html2793" HREF="page72.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page72.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="tex2html2803" 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="tex2html2804" 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="SECTION004430000000000000000">Example-Fibonacci Numbers</A></H2>
<A NAME="secfibonacci">&#160;</A>
<P>
In this section we will compare the asymptotic running times
of two different programs that both compute Fibonacci numbers.<A NAME="tex2html91" HREF="footnode.html#2168" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#2168"><IMG  ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A>
The <em>Fibonacci numbers</em><A NAME=1962>&#160;</A>
are the series of numbers  <IMG WIDTH=16 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline60409" SRC="img471.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img471.gif"  >,  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline60411" SRC="img472.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img472.gif"  >, ..., given by
<P><A NAME="eqnasymptoticfibonacci">&#160;</A> <IMG WIDTH=500 HEIGHT=66 ALIGN=BOTTOM ALT="equation1963" SRC="img473.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img473.gif"  ><P>
Fibonacci numbers are interesting because they seem to crop up
in the most unexpected situations.
However, in this section, we are merely concerned with writing
an algorithm to compute  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline60413" SRC="img474.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img474.gif"  > given <I>n</I>.
<P>
Fibonacci numbers are easy enough to compute.
Consider the sequence of Fibonacci numbers
<P> <IMG WIDTH=345 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath60403" SRC="img475.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img475.gif"  ><P>
The next number in the sequence is computed simply by adding together
the last two numbers--in this case it would be 55=21+34.
Program&nbsp;<A HREF="page73.html#progfibonacci1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#progfibonacci1c"><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> is a direct implementation of this idea.
The running time of this algorithm is clearly <I>O</I>(<I>n</I>)
as shown by the analysis in Table&nbsp;<A HREF="page73.html#tblfibonacci1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#tblfibonacci1c"><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>.
<P>
<P><A NAME="1975">&#160;</A><A NAME="progfibonacci1c">&#160;</A> <IMG WIDTH=575 HEIGHT=238 ALIGN=BOTTOM ALT="program1972" SRC="img476.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img476.gif"  ><BR>
<STRONG>Program:</STRONG> Non-recursive program to compute Fibonacci numbers<BR>
<P>
<P>
<P><A NAME="2170">&#160;</A>
<P>
    <A NAME="tblfibonacci1c">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=LEFT>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	    statement </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> time </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5a </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5b </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60427" SRC="img477.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img477.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5c </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=171 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60429" SRC="img478.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img478.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=171 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60429" SRC="img478.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img478.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    8 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=171 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60429" SRC="img478.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img478.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    9 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=171 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60429" SRC="img478.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img478.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    11 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time
	of Program&nbsp;<A HREF="page73.html#progfibonacci1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#progfibonacci1c"><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></CAPTION></TABLE>
</P></DIV><P>
<P>
Recall that the Fibonacci numbers are defined recursively:
 <IMG WIDTH=129 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline60441" SRC="img479.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img479.gif"  >.
However, the algorithm used in Program&nbsp;<A HREF="page73.html#progfibonacci1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#progfibonacci1c"><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> 
is non-recursive<A NAME=1996>&#160;</A>--it is <em>iterative</em><A NAME=1998>&#160;</A>.
What happens if instead of using the iterative algorithm,
we use the definition of Fibonacci numbers to implement directly
a recursive algorithm<A NAME=1999>&#160;</A>?
Such an algorithm is given in Program&nbsp;<A HREF="page73.html#progfibonacci2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#progfibonacci2c"><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 its running time is summarized in Table&nbsp;<A HREF="page73.html#tblfibonacci2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#tblfibonacci2c"><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>.
<P>
<P><A NAME="2005">&#160;</A><A NAME="progfibonacci2c">&#160;</A> <IMG WIDTH=575 HEIGHT=143 ALIGN=BOTTOM ALT="program2002" SRC="img480.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img480.gif"  ><BR>
<STRONG>Program:</STRONG> Recursive program to compute Fibonacci numbers<BR>
<P>
<P>
<P><A NAME="2172">&#160;</A>
<P>
    <A NAME="tblfibonacci2c">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	    </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=2> time</TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<P>
	    statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>n</I><I>&lt;</I>2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60445" SRC="img481.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img481.gif"  > </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> -- </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> -- </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>T</I>(<I>n</I>-1)+<I>T</I>(<I>n</I>-2)+<I>O</I>(1) </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>T</I>(<I>n</I>-1)+<I>T</I>(<I>n</I>-2)+<I>O</I>(1) </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time of
	Program&nbsp;<A HREF="page73.html#progfibonacci2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#progfibonacci2c"><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></CAPTION></TABLE>
</P></DIV><P>
<P>
From Table&nbsp;<A HREF="page73.html#tblfibonacci2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html#tblfibonacci2c"><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 find that the running
time of the recursive Fibonacci algorithm is given by the recurrence
<P> <IMG WIDTH=409 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath60404" SRC="img482.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img482.gif"  ><P>
But how do you solve a recurrence containing big oh expressions?
<P>
It turns out that there is a simple trick we can use to solve
12 下一页
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -