算法的性能评价

算法其实就是解决问题的一种方法,一个问题的解决往往可以采用多种方法,但每种方法所用的时间和得到的效果往往是不一样的。从前面的统筹安排的例子可以看出,好的算法执行效率高,所耗费的时间短;差的算法则往往需要耗费更多的时间,从而导致效率很低。
算法的一个重要任务便是找到合适的、效率最高的解决问题的方法,即最好的算法。从理论上来讲,这就是需要对算法的性能有一个合理的评价。一个算法的优劣往往通过算法复杂度来衡量,算法复杂度包括时间复杂度和空间复杂度两个方面。
1.时间复杂度
时间度咋读即通常所说的算法执行所需要耗费的时间,时间越短,算法越好。一个算法执行的时间往往无法精确估计,通常需要在实际的计算机中运行才能够知道。但是,也可以对算法的代码进行估计,而得到算法的时间复杂度。
首先,算法代码执行的时间往往和算法代码中语句执行的数量有关。由于每条语句执行都需要时间,语句执行的次数越多,整个程序所耗费的时间就越长。因此,简短、精悍的算法程序往往执行速度快。
另外,算法的时间复杂度还与问题的规模有关。这方面在专门的算法分析中有详细的分析,这里限于篇幅就不在详述了。有兴趣的读者可以参阅算法分析相关的书籍。
2.空间复杂度
空间复杂度指的是算法程序在计算机中执行所需要消耗的存储空间。空间复杂度其实可以分为以下两个方面:
程序保存所需要的存储空间,即程序大小。
程序在执行过程中所需要消耗的存储空间资源,如程序在执行过程中的中坚变量等。