📄 page75.html
字号:
<HTML><HEAD><TITLE>Example-Fibonacci 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="tex2html2072" HREF="page76.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2070" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2064" HREF="page74.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html2074" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION003430000000000000000">Example-Fibonacci Numbers</A></H2><A NAME="secfibonacci"> </A><P>In this section we will compare the asymptotic running timesof two different programs that both compute Fibonacci numbers.<A NAME="tex2html94" HREF="footnode.html#2253"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>The <em>Fibonacci numbers</em><A NAME=2047> </A>are the series of numbers <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59867" SRC="img467.gif" >, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59869" SRC="img468.gif" >, ..., given by<P><A NAME="eqnasymptoticfibonacci"> </A> <IMG WIDTH=500 HEIGHT=67 ALIGN=BOTTOM ALT="equation2048" SRC="img469.gif" ><P>Fibonacci numbers are interesting because they seem to crop upin the most unexpected situations.However, in this section, we are merely concerned with writingan algorithm to compute <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif" > given <I>n</I>.<P>Fibonacci numbers are easy enough to compute.Consider the sequence of Fibonacci numbers<P> <IMG WIDTH=346 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath59861" SRC="img471.gif" ><P>The next number in the sequence is computed simply by adding togetherthe last two numbers--in this case it is 55=21+34.Program <A HREF="page75.html#progexamplel"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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 <A HREF="page75.html#tblfibonacci1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="2060"> </A><A NAME="progexamplel"> </A> <IMG WIDTH=575 HEIGHT=199 ALIGN=BOTTOM ALT="program2057" SRC="img472.gif" ><BR><STRONG>Program:</STRONG> Non-recursive program to compute Fibonacci numbers.<BR><P><P><P><A NAME="2255"> </A><P> <A NAME="tblfibonacci1c"> </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>2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>O</I>(1) </TD></TR><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> 5 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59885" SRC="img473.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=171 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59887" SRC="img474.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_inline59887" SRC="img474.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_inline59887" SRC="img474.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_inline59887" SRC="img474.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </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 <A HREF="page75.html#progexamplel"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>Recall that the Fibonacci numbers are defined recursively: <IMG WIDTH=129 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline59899" SRC="img475.gif" >.However, the algorithm used in Program <A HREF="page75.html#progexamplel"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is non-recursive<A NAME=2081> </A>--it is <em>iterative</em><A NAME=2083> </A>.What happens if instead of using the iterative algorithm,we use the definition of Fibonacci numbers to implement directlya recursive algorithm<A NAME=2084> </A>?Such an algorithm is given in Program <A HREF="page75.html#progexamplem"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and its running time is summarized in Table <A HREF="page75.html#tblfibonacci2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="2090"> </A><A NAME="progexamplem"> </A> <IMG WIDTH=575 HEIGHT=105 ALIGN=BOTTOM ALT="program2087" SRC="img476.gif" ><BR><STRONG>Program:</STRONG> Recursive program to compute Fibonacci numbers.<BR><P><P><P><A NAME="2257"> </A><P> <A NAME="tblfibonacci2c"> </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><</I>2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59903" SRC="img477.gif" > </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>2 </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> 3 </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> 5 </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 <A HREF="page75.html#progexamplem"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>From Table <A HREF="page75.html#tblfibonacci2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we find that the runningtime of the recursive Fibonacci algorithm is given by the recurrence<P> <IMG WIDTH=410 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath59862" SRC="img478.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 solvea recurrence containing big oh expressions<em>as long as we are only interested in an asymptotic bound on the result</em>.Simply drop the <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >s from the recurrence,⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -