Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 算法复杂性渐近阶的分析
发信站: 哈工大紫丁香 (2002年03月22日14:39:36 星期五), 站内信件

算法复杂性渐近阶的分析
前两段讲的是算法复杂性渐近阶的概念和对它进行分析的重要性。本段要讲如何具体地
分析一个算法的复杂性的渐近阶，给出一套可操作的规则。算法最终要落实到用某种程
序设计语言（如Pascal）编写成的程序。因此算法复杂性渐近阶的分析可代之以对表达
该算法的程序的复杂性渐近阶的分析。
如前所提出，对于算法的复杂性，我们只考虑最坏、最好和平均三种情况，而通常又着
重于最坏情况。为了明确起见，本段限于针对最坏情况。
仍然以时间复杂性为例。这里给出分析时间复杂性渐近阶的八条规则。这八条规则已覆
盖了用Pascal语言程序所能表达的各种算法在最坏情况下的时间复杂性渐近阶的分析。

在逐条地列出并解释这入条规则之前，应该指出，当我们分析程序的某一局部(如一个语
句，一个分程序，一个程序段，一个过程或函数)时，可以用具体程序的输入的规模N作
为复杂性函数的自变量，也可以用局部的规模参数作为自变量。但是，作为最终结果的
整体程序的复杂性函数只能以整体程序的输入规模为自变量。
对于串行的算法，相应的Pascal程序是一个串行的Pascal语句序列，因此，很明显，该
算法的时间复杂性(即所需要的时间)等于相应的Pascal程序的每一个语句的时间复杂性
(即所需要的时间)之和。所以，如果执行Pascal语句中的每一种语句所需要的时间都有
计量的规则，那么，执行一个程序，即执行一个算法所需要的时间的计量便只是一个代
数问题。接着，应用本节第三段所提供的Ο、Ω和θ等运算规则就可以分析出算法时间
复杂性的渐近阶。
因此，我们的时间计量规则只需要针对Pascal有限的几种基本运算和几种基本语句。下
面是这些规则的罗列和必要的说明。
规则(1)
赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等，只需要1个单位时间。

规则(2)
条件语句"if C then S1 else S2"只需要Tc+max(Ts1，Ts2)的时间，其中Tc是计算条件
表达式C需要的时间，而Ts1和Ts2分别是执行语句S1和S2需要的时间。
规则(3)
选择语句"Case  A  of  a1:S1; a2:S2; … ;am:Sm;  end"，需要max(Ts1, Ts2，…，
Tsm)的时间，其中Tsii是执行语句Si所需要的时间，i=l,2,…,m。
规则(4)
访问一个数组的单个分量或一个记录的单个域，只需要1个单位时间。
规则(5)
执行一个for循环语句需要的时间等于执行该循环体所需要的时间乘上循环的次数。
规则(6)
执行一个while循环语句"while C do S"或一个repeat循环语句" repeat S until C"，
需要的时间等于计算条件表达式C需要的时间与执行循环S体需要的时间之和乘以循环的
次数。与规则5不同，这里的循环次数是隐含的。
例如，b_search函数中的while循环语句。按规则(1)-(4)，计算条件表达式" (not fou
nd)and(U≥=L)"与执行循环体
I:=(U+L)div 2;
if c=A[I] then found:=true
          else  if  c>A[I] then L:=I+1
                           else U:=I-1;
只需要θ(1)时间，而循环次数为logm，所以，执行此while语句只需要θ(logm)时间。

在许多情况下，运用规则(5)和(6)常常须要借助具体算法的内涵来确定循环的次数，才
不致使时间的估计过于保守。这里举一个例子。
考察程序段：
　 　
Size:=m;
 1
i:=1;
 1
while i<n do
    begin
      i:=i+1;
      S1;
 θ(n)
      if  Size>0  then
 1
         begin
         在1到Size的范围内任选一个数赋值给t;
 θ(1)
             Size:=Size-t;
 2
             for j:=l  to  t  do
                 S2
 θ(n)
         end;
    end;
　 　
程序在各行右端顶格处标注着执行相应各行所需要的时间。如果不对算法的内涵作较深
入的考察，只看到1≤t≤Size≤m，就草率地估计while的内循环for的循环次数为Ο(m)
，那么，程序在最坏情况下的时间复杂性将被估计为Ο(n 2+m·n 2)。反之，如果对算
法的内涵认真地分析，结果将两样。事实上，在while的循环体内t是动态的,size也是动
态的，它们都取决while的循环参数i，即t=t(i)记为ti；size=size(i)记为sizei ，i=
l,2,…,n-1。对于各个i，1≤i≤n-1，ti与m的关系是隐含的，这给准确地计算for循环
的循环体S2被执行的次数带来困难。上面的估计比较保守的原因在于我们把S2的执行次
数的统计过于局部化。如果不局限于for循环，而是在整个程序段上统计S2被执行的总次
数，那么，这个总次数等于，又根据算法中ti的取法及sizei+1=sizei-ti，i=1,2,…,n
-1 有sizen=size1-。最后利用size1=m和sizen=0得到=m 。于是在整个程序段上，S2被
执行的总次数为m，所需要的时间为θ(mn)。执行其他语句所需要的时间直接运用规则(
l)-(6)容易计算。累加起来，整个程序段在最坏情况下时间复杂性渐近阶为θ(n 2+mn)
。这个结果显然比前面粗糙的估计准确。
规则(7)
对于goto语句。在Pascal中为了便于表达从循环体的中途跳转到循环体的结束或跳转到
循环语句的后面语句，引入goto语句。如果我们的程序按照这一初衷使用goto语句，那
么，在时间复杂性分析时可以假设它不需要任何额外的时间。因为这样做既不会低估也
不会高估程序在最坏情况下的运行时间的阶。如果有的程序滥用了goto语句，即控制转
移到前面的语句，那么情况将变得复杂起来。当这种转移造成某种循环时，只要与别的
循环不交叉，保持循环的内外嵌套，则可以比照规则(1)-(6)进行分析。当由于使用got
o语句而使程序结构混乱时，建议改写程序然后再做分析。
规则(8)
对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移
，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里
向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求
。如果过程(或函数)出现直接或间接的递归调用，则上述由里向外逐层剥的分析行不通
。这时我们可以对其中的各个递归过程(或函数)，所需要的时间假设为一个相应规模的
待定函数。然后一一根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到
递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。
递归方程的种类很多，求它们的解的渐近阶的方法也很多，我们将在下一段比较系统地
给予介绍。本段只举一个简单递归过程(或函数)的例子来说明如何建立相应的递归方程
，同时不加推导地给出它们在最坏情况下的时间复杂性的渐近阶。
例：再次考察函数b_search，这里将它改写成一个递归函数。为了简明，我们已经运用
前面的规则(l)-(6)，统计出执行各行语句所需要的时间，并标注在相应行的右端：
　
 　
Function b_search(C,L,U:integer):integer;
 单位时间数
var index,element:integer;
 begin
   if (U<L) then
      1
            b_search:=0;
      1
   else
    begin
      index:=(L+U) div 2;
      3
      element:=A[index];
      2
      if element=C then
      1
        b_search:=index
      1
   else if element>C then
        b_search:=b_search(C,L,index-1)
    3+T(m/2)
      else
        b_search:=b_search(C,index+1,U);
    3+T(m/2)
    end;
 end;
　 　
其中T(m)是当问题的规模U-L+1=m时b_search在最坏情况下(这时，数组A[L..U]中没有给
定的C)的时间复杂性。根据规则(l)-(8)，我们有：
或化简为
这是一个关于T(m)的递归方程。用下一段将介绍的迭代法，容易解得：
T(m)=11logm +l3=θ(logm)
在结束这一段之前，我们要提一下关于算法在最坏情况下的空间复杂性分析。我们照样
可以给出与分析时间复杂性类似的规则。这里不赘述。然而应该指出，在出现过程(或函
数)递归调用时要考虑到其中隐含的存储空间的额外开销。因为现有的实现过程(或函数
)递归调用的编程技术需要一个隐含的、额外(即不出现在程序的说明中)的栈来支持。过
程(或函数)的递归调用每深人一层就把本层的现场局部信息及调用的返回地址存放在栈
顶备用，直到调用的最里层。因此递归调用一个过程(或函数)所需要的额外存储空间的
大小即栈的规模与递归调用的深度成正比，其比例因子等于每深入一层需要保存的数据
量。比如本段前面所举的递归函数b_search，在最坏情况下，递归调用的深度为logm，
因而在最坏情况下调用它所需要的额外存储空间为θ(logm)。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]