Control 版 (精华区)

发信人: doer (老三： 醉亦何妨), 信区: Control
标  题: 算法复杂性3(转载)
发信站: 哈工大紫丁香 (2002年06月08日10:41:20 星期六), 转信

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 longforyou 所发表 】
  复杂性的计量
算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性
，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用
的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依
赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算
法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：

C =F(N,I,A)

其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分
别用T和S来表示，那么应该有：

T =T(N,I,A) (2.1)

和 S =S(N,I,A) (2.2)

通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为

T =T(N,I)

和 S =S(N,I)

由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些
，所以下文将主要地讨论时间复杂性。

下面以T(N,I)为例，将复杂性函数具体化。

根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计
算机所提供的元运算有k种，他们分别记为O1,O2 ,..,Ok；再设这些元运算每执行一次所需
要的时间分别为t1,t2,..,tk 。对于给定的算法A，设经过统计，用到元运算Oi的次数为e
i，i=1,2,..,k ，很明显，对于每一个i，1<=i<=k，ei是N和I的函数，即ei=ei(N,I)。那
么有：

 (2.3)

其中ti，i=1,2,..,k,是与N,I无关的常数。

显然，我们不可能对规模N的每一种合法的输入I都去统计ei(N,I),i=1,2,…,k。因此T(N,
I)的表达式还得进一步简化，或者说，我们只能在规模为N的某些或某类有代表性的合法输
入中统计相应的ei , i=1,2,…,k，评价时间复杂性。

下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分
别记为Tmax(N )、Tmin(N)和Tavg(N )。在数学上有：

 (2.4)

 (2.5)

 (2.6)

其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入
，是DN中一个使T(N,)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率
。

以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有
各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。
下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。

一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定
的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确
定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如
等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平
均情况下的时间复杂性分析还仅仅是停留在理论上。

现在以上一章提到的问题1的算法Search为例来说明如何利用(2.4)-(2.6)对它的Tmax、Tm
in和Tavg进行计量。这里问题的规模以m计算，算法重用到的元运算有赋值、测试和加法等
三种，它们每执行一次所需的时间常数分别为a,t,和s 。对于这个例子，如假设c在A中，
那么容易直接看出最坏情况的输入出现在c=A[m]的情形，这时：

Tmax(m)=a+2mt+(m-1)s+(m-1)a+t+a=(m+1)a+(2m+1)t+(m-1)s (2.7)

而最好情况的输入出现在c=A[1]的情形。这时：

 (2.8)

至于Tavg(m)，如前所述，必须对Dm上的概率分布做出假设才能计量。为简单起见，我们做
最简单的假设：Dm上的概率分布是均等的，即P(A[i]=c)=1/m 。若记Ti=T(m,Ii)，其中Ii
表示A[i]=c的合法输入，那么：

 (2.9)

而根据与(2.7)类似的推导，有：



代入(2.9) ，则：



这里碰巧有：

Tavg(m)=(Tmax(m)+Tmin(m))/2

但必须指出，上式并不具有一般性。

类似地，对于算法B_Search照样可以按(2.4)-(2.6)计算相应的Tmax(m)、Tmin(m)和Tavg(
m) 。不过，我们这里只计算Tmax(m) 。为了与Search比较，仍假设c在A中，即最坏情况的
输入仍出现在c=A[m]时。这时，while循环的循环体恰好被执行了logm +1 即k+1 次。因为
第一次执行时数据的规模为m，第二次执行时规模为m/2等等，最后一次执行时规模为1。另
外，与Search少有不同的是这里除了用到赋值、测试和加法三种原运算外，还用到减法和
除法两种元运算。补记后两种元运算每执行一次所需时间为b和d ，则可以推演出：

 (2.10)

比较(2.7)和(2.10) ，我们看到m充分大时，在最坏情况下B_Search的时间复杂性远小于S
earch的时间复杂性。




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 61.156.24.116]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shao.hit.edu.cn]