Algorithm 版 (精华区)

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

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

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

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