一个好的算法往往可以使程序运行的更快,衡量一个算法的好坏往往将算法效率和存储空间作为重要依据。算法的效率需要通过算法编制的程序在计算机上的运行时间来衡量,存储空间需求通过算法在执行过程中所占用的最大存储空间来衡量。本节主要介绍算法设计的要求、算法效率评价、算法的时间复杂度及算法的空间复杂度。
一个好的算法应该具备以下目标。
算法的 正确性 (correctness)是指算法至少应该包括对于输入、输出和加工处理无歧义性的描述,能正确反映问题的需求,且能够得到问题的正确答案。
通常算法的正确性应包括以下4个层次。
(1)算法对应的程序没有语法错误。
(2)对于几组输入数据能得到满足规格要求的结果。
(3)对于精心选择的典型的、苛刻的带有刁难性的几组输入数据能得到满足规格要求的结果。
(4)对于一切合法的输入都能得到产生满足要求的结果。
对于这4层算法正确性的含义,达到第4层意义上的正确是极为困难的,所有不同输入数据的数量大得惊人,逐一验证的方法是不现实的。一般情况下,我们把层次3作为衡量一个程序是否正确的标准。
算法主要是为了人们方便阅读和交流,其次才是计算机执行。 可读性 (readability)好有助于人们对算法的理解,晦涩难懂的程序往往隐含错误不易被发现,难以调试和修改。
当输入数据不合法时,算法也应该能做出反应或进行处理,而不会产生异常或莫名其妙的输出结果。例如,求一元二次方程根ax 2 +bx+c=0的算法,需要考虑多种情况,先判断b 2 -4ac的正负,如果为正数,则该方程有两个不同的实根;如果为负,表明该方程无实根;如果为零,表明该方程只有一个实根;如果a=0,则该方程又变成了一元一次方程,此时若b=0,还要处理除数为零的情况。如果输入的a、b、c不是数值型,还要提示用户输入错误。
效率指的是算法的执行时间。对于同一个问题如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的效率低。存储量需求指算法在执行过程中需要的最大存储空间。效率与低存储量需求都与问题的规模有关,求100个人的平均分与求1000个人的平均分所花的执行时间和运行空间显然有一定差别。设计算法时应尽量选择高效率和低存储量需求的算法。
算法执行时间需通过依据该算法编制的程序在计算机上的运行时所耗费的时间来度量,而度量一个算法在计算机上的执行时间通常有如下两种方法。
目前计算机内部大都有计时功能,有的甚至可精确到毫秒级,不同算法的程序可通过一组或若干组相同的测试程序和数据以分辨算法的优劣。但是,这种方法有两个缺陷,一是必须依据算法事先编制好程序,这通常需要花费大量的时间与精力;二是时间的长短依赖计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣。因此,人们常常采用事前分析估算的方法评价算法的好坏。
这主要在计算机程序编制前,对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素。
·算法采用的策略、方法。
·编译产生的代码质量。
·问题的规模。
·书写的程序语言,对于同一个算法,语言级别越高,执行效率越低。
·机器执行指令的速度。
在以上5个因素中,算法采用的不同的策略,或不同的编译系统,或不同的语言实现,或在不同的机器运行时,效率都不相同。抛开以上因素,算法效率则可以通过问题的规模来衡量。
一个算法由控制结构(顺序、分支和循环结构)和基本语句(赋值语句、声明语句和输入输出语句)构成,则算法的运行时间取决于两者执行时间的总和,所有语句的执行次数可以作为语句的执行时间的度量。语句的重复执行次数称为语句频度。
例如,斐波那契数列的算法和语句的频度如下。
每一条语句的频度 f0=0; 1 f1=1; 1 printf("%d,%d",f0,f1); 1 for(i=2;i<=n;i++) n { fn=f0+f1; n-1 printf(",%d",fn); n-1 f0=f1; n-1 f1=fn; n-1 }
每一条语句的右端是对应语句的 频度 (frequency count),即语句的执行次数。上面算法总的执行次数为T(n)=1+1+1+n+4(n-1)=5n-1。
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是 算法 的时间量度 ,记作T(n)=O(f(n))。
它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的 渐进时间复杂度 (asymptotic time complexity),简称为 时间复杂度 。其中,f(n)是问题规模n的某个函数。
一般情况下,随着n的增大,T(n)的增长较慢的算法为最优的算法。例如,在下列三段程序段中,给出原操作x=x+1的时间复杂度分析。
(1)
1 ;
(2)
for (i=1 ;i<=n ;i++ ) x=x+1 ;
(3)
for (i=1 ;i<=n ;i++ ) for (j=1 ;j<=n ;j++ ) x=x+1 ;
程序段(1)的时间复杂度为O(1),称为常量阶;程序段(2)的时间复杂度为O(n),称为线性阶;程序段(3)的时间复杂度为O(n 2 ),称为平方阶。此外算法的时间复杂度还有对数阶O(log 2 n)、指数阶O(2 n )等。
上面的斐波那契数列的时间复杂度T(n)=O(n)。
常用的时间复杂度所耗费的时间从小到大依次是O(1)<O(log 2 n)<O(n)<O(n 2 )<O(n 3 )<O(2 n )<O(n!)。
算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下,具有指数级的时间的复杂度算法只有当n足够小时才是可使用的算法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度算法是常用的算法。一些常见函数的增长率如图1-10所示。
图1-10 常见函数的增长率
一般情况下,算法的时间复杂度只需要考虑关于问题规模n的增长率或阶数。例如以下程序段。
for(i=2;i<=n;i++) for(j=2;j<=i-1;j++) { k++; a[i][j]=x; }
语句k++的执行次数关于n的增长率为n 2 ,它是语句频度(n-1)(n-2)/2中增长最快的项。
在有些情况下,算法的基本操作的重复执行次数还依赖于输入的数据集。例如如下冒泡排序算法。
void BubbleSort(int a[],int n) { int i,j,t; change=TRUE; for(i=1;i<=n-1&&change;i++) { change=FALSE; for(j=1;j<=n-i;j++) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; change=TRUE; } } }
交换相邻两个整数为该算法中的基本操作。当数组a中的初始序列为从小到大有序排列时,基本操作的执行次数为0;当数组中初始序列从大到小排列时,基本操作的执行次数为n(n-1)/2。对这类算法的分析,一种方法是计算所有情况的平均值,这种时间复杂的计算方法称为平均时间复杂度;另外一种方法是计算最坏情况下的时间复杂度,这种方法称为最坏时间复杂度。若数组a中初始输入数据可能出现n!种的排列情况的概率相等,则冒泡排序的平均时间复杂度为T(n)=O(n 2 )。
然而,在很多情况下,各种输入数据集出现的概率难以确定,算法的平均复杂度也就难以确定。因此,另一种更可行也更为常用的办法是讨论算法在最坏情况下的时间复杂度,即分析最坏情况以估算算法执行时间的上界。例如,上面冒泡排序的最坏时间复杂度为数组a中初始序列为从大到小有序,则冒泡排序算法在最坏情况下的时间复杂度为T(n)=O(n 2 )。一般情况下,本书以后讨论的时间复杂度,在没有特殊说明情况下,都指的是最坏情况下的时间复杂度。
空间复杂度 (space complexity)作为算法所需存储空间的量度,记做S(n)=O(f(n))。其中,n为问题的规模,f(n)为语句关于n的所占存储空间的函数。一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。