< >程序在各行右端顶格处标注着执行相应各行所需要的时间。如果不对算法的内涵作较深入的考察，只看到1≤<I>t</I>≤Size≤<I>m</I>，就草率地估计while的内循环for的循环次数为<I>Ο</I>(<I>m</I>)，那么，程序在最坏情况下的时间复杂性将被估计为<I>Ο</I>(<I>n</I><SUP> 2</SUP>+<I>m</I>·<I>n</I><SUP> 2</SUP>)。反之，如果对算法的内涵认真地分析，结果将两样。事实上，在while的循环体内<I>t</I>是动态的,size也是动态的，它们都取决while的循环参数i，即<I>t</I>=<I>t</I>(i)记为<I>t</I><SUB>i</SUB>；size=size(i)记为size<SUB>i </SUB>，i=l,2,…,<I>n</I>-1。对于各个i，1≤i≤<I>n</I>-1，<I>t</I><SUB>i</SUB>与<I>m</I>的关系是隐含的，这给准确地计算for循环的循环体S<SUB>2</SUB>被执行的次数带来困难。上面的估计比较保守的原因在于我们把S<SUB>2</SUB>的执行次数的统计过于局部化。如果不局限于for循环，而是在整个程序段上统计S<SUB>2</SUB>被执行的总次数，那么，这个总次数等于<SUB><img src="http://algorithm.myrice.com/algorithm/complexity/images/img13.gif"></SUB>，又根据算法中t<SUB>i</SUB>的取法及size<SUB>i+1</SUB>=size<SUB>i</SUB>-t<SUB>i</SUB>，i=1,2,…,n-1 有size<SUB>n</SUB>=size<SUB>1</SUB>-<SUB><img src="http://algorithm.myrice.com/algorithm/complexity/images/img4.gif"></SUB>。最后利用size<SUB>1</SUB>=m和size<SUB>n</SUB>=0得到<SUB><img src="http://algorithm.myrice.com/algorithm/complexity/images/img14.gif"></SUB>=m 。于是在整个程序段上，S<SUB>2</SUB>被执行的总次数为m，所需要的时间为<I>θ</I>(<I>mn</I>)。执行其他语句所需要的时间直接运用规则(l)-(6)容易计算。累加起来，整个程序段在最坏情况下时间复杂性渐近阶为<I>θ</I>(<I>n</I><SUP> 2</SUP>+<I>mn</I>)。这个结果显然比前面粗糙的估计准确。</P><DL><DT><B>规则(7)</B> </DT></DL><>对于goto语句。在Pascal中为了便于表达从循环体的中途跳转到循环体的结束或跳转到循环语句的后面语句，引入goto语句。如果我们的程序按照这一初衷使用goto语句，那么，在时间复杂性分析时可以假设它不需要任何额外的时间。因为这样做既不会低估也不会高估程序在最坏情况下的运行时间的阶。如果有的程序滥用了goto语句，即控制转移到前面的语句，那么情况将变得复杂起来。当这种转移造成某种循环时，只要与别的循环不交叉，保持循环的内外嵌套，则可以比照规则(1)-(6)进行分析。当由于使用goto语句而使程序结构混乱时，建议改写程序然后再做分析。</P><DL><DT><B>规则(8)</B> </DT></DL><>对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则上述由里向外逐层剥的分析行不通。这时我们可以对其中的各个递归过程(或函数)，所需要的时间假设为一个相应规模的待定函数。然后一一根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。</P><P>递归方程的种类很多，求它们的解的渐近阶的方法也很多，我们将在下一段比较系统地给予介绍。本段只举一个简单递归过程(或函数)的例子来说明如何建立相应的递归方程，同时不加推导地给出它们在最坏情况下的时间复杂性的渐近阶。</P><P>例：再次考察函数b_search，这里将它改写成一个递归函数。为了简明，我们已经运用前面的规则(l)-(6)，统计出执行各行语句所需要的时间，并标注在相应行的右端：</P> |
楼主