计算机算法分析与设计论文

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+小的常数Р从表1-1的最后一列可以清楚地看到,对于高效的算法A1,计算机的计算速度增长10倍,可求解的规模同步增长10倍;对于A2,可求解的问题的规模的增长与计算机的计算速度的增长接近同步;但对于低效的算法A3,情况就大不相同,计算机的计算速度增长10倍只换取可求解的问题的规模增加log10。当问题的规模充分大时,这个增加的数字是微不足道的。换句话说,对于低效的算法,计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此,对于低效算法要扩大解题规模,不能寄希望于移植算法到高速的计算机上,而应该把着眼点放在算法的改进上。Р从表1-l的最后一列我们还看到,限制求解问题规模的关键因素是算法渐近复杂性的阶,对于表中的前四种算法,其渐近的时间复杂性与规模N的一个确定的幂同阶,相应地,计算机的计算速度的乘法增长带来的是求解问题的规模的乘法增长,只是随着幂次的提高,规模增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于表中的后两种算法,其渐近的时间复杂性与规模N的一个指数函数同阶,相应地计算机的计算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见,算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。