Control 版 (精华区)

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

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 longforyou 所发表 】
复杂性渐近阶的重要性
计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线
增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行
复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时
间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。
造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要
求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和
规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是超线性的，
决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。事实上，
我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。

我们还是以时间效率为例。设A1,A2,…和A6。是求解同一间题的6个不同的算法，它们的渐
近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机
上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上
算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们
就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,…,6。分别
解出N2i和N1i的关系，可列成下表：

表4-1算法与渐近时间复杂性的关系

算法 渐进时间复杂性T(N) 在C1上可解的规模N1 在C2上可解的规模N2 N1和N2的关系 
A1 N N11 N21 N21=10N11 
A2 NlogN N12 N22 N22≈10N12 
A3 N2 N13 N23  
A4 N3 N14 N24  
A5 2N N15 N25 N25 =N15+log10 
A6 N! N16 N26 N26 =N16+小的常数 

从表4-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可
求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的增
长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长10倍只换取
可求解的问题的规模增加log10。当问题的规模充分大时，这个增加的数字是微不足道的。
换句话说，对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解
规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计算
机上，而应该把着眼点放在算法的改进上。

从表4-l的最后一列我们还看到，限制求解问题规模的关键因素是算法渐近复杂性的阶，对
于表中的前四种算法，其渐近的时间复杂性与规模N的一个确定的幂同阶，相应地，计算机
的计算速度的乘法增长带来的是求解问题的规模的乘法增长，只是随着幂次的提高，规模
增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于
表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶，相应地计算机的计
算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶
的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法
。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性
的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的
渐近阶。

多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多
项式算法，只找到指数型算法。

我们在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：

“复杂性的渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效”这个结论，只是在
问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N 3<2N，即N≥c 时才成立。
其中c是方程N 3=2N的解。当N <c时，A5反而比A4有效。所以对于规模小的问题，不要盲目
地选用复杂性阶比较低的算法。其原因一方面是如上所说，复杂性阶比较低的算法在规模
小时不一定比复杂性阶比较高的算法更有效；另方面，在规模小时，决定工作效率的可能
不是算法的效率而是算法的简单性，哪一种算法简单，实现起来快，就选用那一种算法。
 
当要比较的两个算法的渐近复杂性的阶相同时，必须进一步考察渐近复杂性表达式中常数
因子才能判别它们谁好谁差。显然常数因子小的优于常数因子大的算法。比如渐近复杂性
为N1ogN/l00的算法显然比渐近复杂性为l00NlogN的算法来得有效。



--

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