算法效率是指算法执行的时间,算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中,比较少需要考虑这个问题了,特别是pc机的编程,内存空间越来越大,所以被考虑得也越来越少,不过一个好的程序员,都应该对自己的程序有要求,每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解,能够大概的去运用"效率度量"还是有很大意义的。
度量一个程序的执行时间通常有两种方法:(一)事后统计的方法(二)事前分析估算的方法。
事后统计的方法不利于较大范围内的算法比较(异地,异时,异境)。
事前分析估算的方法与许多因素有关,包括算法本身选用的策略、问题的规模、书写程序的语言、编译产生的机器代码质量和机器执行指令的速度等。为便于比较算法本身的优劣,应排除其它影响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间量。(原操作在所有该问题的算法中都相同)
度量一个程序运行时间的方式通过时间复杂度和空间复杂度来表征。
上式表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。
上式表示空间复杂度。空间复杂度可以作为算法所需存储空间的量度。若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。原地工作意思是一个算法需要少量的辅助空间,且其大小不随问题规模的大小而改变。如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析 。
最差效率:指当输入规模为n时,算法的最坏情况下的效率。
最优效率:指当输入规模为n时,算法在最优情况下的效率。
平均效率:指当输入规模为n时,算法的平均效率。
大量实践经验告诉我们,我们评价一个算法是应该重点考虑最差效率这一点。