📄 page456.html
字号:
<HTML><HEAD><TITLE>Summary</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="tex2html6423" HREF="page457.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6421" HREF="page452.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6417" HREF="page455.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6425" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H4><A NAME="SECTION0014340400000000000000">Summary</A></H4><P>For many divide-and-conquer algorithmsthe running time is given by the general recurrenceshown in Equation <A HREF="page452.html#eqnalgsdandq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Solutions to the recurrence depend on the relativevalues of the constants <I>a</I>, <I>b</I>, and <I>k</I>.Specifically, the solutions satisfy the following bounds:<P><A NAME="eqnalgsdandqsoln"> </A> <IMG WIDTH=500 HEIGHT=67 ALIGN=BOTTOM ALT="equation32924" SRC="img1805.gif" ><P><P>Table <A HREF="page456.html#tblalgstimes2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how to apply Equation <A HREF="page456.html#eqnalgsdandqsoln"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>to find the running times of the divide-and-conquer algorithmsdescribed in the preceding sections.Comparing the solutions in Table <A HREF="page456.html#tblalgstimes2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> with thosegiven in Table <A HREF="page452.html#tblalgstimes"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the results obtained usingthe general formula agree with the analyses done in the preceding sections.<P><P><A NAME="33455"> </A><P> <A NAME="tblalgstimes2"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=7 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=LEFT><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> program </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> recurrence </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>a</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>k</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> case </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> solution </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>Program <A HREF="page449.html#progexampleo"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>T</I>(<I>n</I>)=<I>T</I>(<I>n</I>/2)+<I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=43 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68049" SRC="img1799.gif" > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=82 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68079" SRC="img1806.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> Program <A HREF="page450.html#progexamplep"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>T</I>(<I>n</I>)=2<I>T</I>(<I>n</I>/2)+<I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=43 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68035" SRC="img1793.gif" > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=65 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68085" SRC="img1807.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> Program <A HREF="page451.html#progexampleq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>T</I>(<I>n</I>)=2<I>T</I>(<I>n</I>/2)+<I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=43 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68049" SRC="img1799.gif" > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <IMG WIDTH=82 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68091" SRC="img1808.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing running times using Equation <A HREF="page456.html#eqnalgsdandqsoln"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html6423" HREF="page457.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6421" HREF="page452.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6417" HREF="page455.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6425" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -