📄 page452.html
字号:
<HTML><HEAD><TITLE>Running Time of Divide-and-Conquer Algorithms</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="tex2html6377" HREF="page453.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6375" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6369" HREF="page451.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6379" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014340000000000000000">Running Time of Divide-and-Conquer Algorithms</A></H2><P>A number of divide-and-conquer algorithms are presentedin the preceding sections.Because these algorithms have a similar form,the recurrences which give the running times of the algorithmsare also similar in form.Table <A HREF="page452.html#tblalgstimes"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizes the running timesof Programs <A HREF="page449.html#progexampleo"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page450.html#progexamplep"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page451.html#progexampleq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="32808"> </A><P> <A NAME="tblalgstimes"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=LEFT><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=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=LEFT NOWRAP> <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.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=LEFT NOWRAP> <I>O</I>(<I>n</I>) </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=LEFT NOWRAP> <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Running times of divide-and-conquer algorithms.</CAPTION></TABLE></P></DIV><P><P>In this section we develop a general recurrencethat characterizes the running times of many divide-and-conquer algorithms.Consider the form of a divide-and-conquer algorithm to solve a given problem.Let <I>n</I> be a measure of the size of the problem.Since the divide-and-conquer paradigm is essentially recursive,there must be a base case.That is, there must be some value of <I>n</I>, say <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif" >,for which the solution to the problem is computed directly.We assume that the worst-case running time for the base caseis bounded by a constant.<P>To solve an arbitrarily large problem using divide-and-conquer,the problem is <em>divided</em> into a number smaller problems,each of which is solved independently.Let <I>a</I> be the number of smaller problems to be solved( <IMG WIDTH=38 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67995" SRC="img1779.gif" >, <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67997" SRC="img1780.gif" >).The size of each of these problems is some fraction ofthe original problem,typically either <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67999" SRC="img1781.gif" > or <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68001" SRC="img1782.gif" >( <IMG WIDTH=36 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68003" SRC="img1783.gif" >, <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68005" SRC="img1784.gif" >).<P>The solution to the original problem is constructedfrom the solutions to the smaller problems.The running time required to do this depends on the problem to be solved.In this section we consider polynomial running times.That is, <IMG WIDTH=41 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60361" SRC="img575.gif" > for some integer <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.<P>For the assumptions stated above,the running time of a divide-and-conquer algorithm is given by<P><A NAME="eqnalgsdandq"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation32820" SRC="img1785.gif" ><P><P>In order to make it easier to find the solution to Equation <A HREF="page452.html#eqnalgsdandq"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we drop the <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >s as well as the <IMG WIDTH=14 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57945" SRC="img105.gif" > from the recurrence.We can also assume (without loss of generality) that <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58989" SRC="img345.gif" >.As a result, the recurrence becomes<P> <IMG WIDTH=359 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath67973" SRC="img1786.gif" ><P><P>Finally, we assume that <I>n</I> is a power of <I>b</I>.That is, <IMG WIDTH=49 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68021" SRC="img1787.gif" > for some integer <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68023" SRC="img1788.gif" >.Consequently, the recurrence formula becomes<P><A NAME="eqnalgsi"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation32828" SRC="img1789.gif" ><P><P>We solve Equation <A HREF="page452.html#eqnalgsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> as follows.Divide both sizes of the recurrence by <IMG WIDTH=19 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68025" SRC="img1790.gif" >and then <em>telescope</em><A NAME=32837> </A>:<P><A NAME="eqnalgsiii"> </A><A NAME="eqnalgsii"> </A> <IMG WIDTH=500 HEIGHT=215 ALIGN=BOTTOM ALT="eqnarray32838" SRC="img1791.gif" ><P><P>Adding Equation <A HREF="page452.html#eqnalgsii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> through Equation <A HREF="page452.html#eqnalgsiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,substituting <I>T</I>(1)=1and multiplying both sides by <IMG WIDTH=19 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68025" SRC="img1790.gif" > gives<P><A NAME="eqnalgsiv"> </A> <IMG WIDTH=500 HEIGHT=47 ALIGN=BOTTOM ALT="equation32869" SRC="img1792.gif" ><P>In order to evaluate the summation in Equation <A HREF="page452.html#eqnalgsiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>we must consider three cases:<P><BR> <HR><UL> <LI> <A NAME="tex2html6380" HREF="page453.html#SECTION0014340100000000000000">Case 1 ( <IMG WIDTH=43 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68035" SRC="img1793.gif" >)</A><LI> <A NAME="tex2html6381" HREF="page454.html#SECTION0014340200000000000000">Case 2 ( <IMG WIDTH=43 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68049" SRC="img1799.gif" >)</A><LI> <A NAME="tex2html6382" HREF="page455.html#SECTION0014340300000000000000">Case 3 ( <IMG WIDTH=43 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline68059" SRC="img1802.gif" >)</A><LI> <A NAME="tex2html6383" HREF="page456.html#SECTION0014340400000000000000">Summary</A></UL><HR><A NAME="tex2html6377" HREF="page453.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6375" HREF="page448.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6369" HREF="page451.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6379" 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 + -