第2章 算法分析

算法分析

算法分析是指对一个算法所需要的资源进行预测。资源包括存储、传输和计算资源等，但在算法分析中通常只重点关注时间与空间方面的资源。给定一个问题，一般都会有多种候选算法可以解决该问题，那么通过对这些算法进行分析，可以从中选择出一个最有效的算法，或者排除掉较差的算法。好的算法，应该具有正确性、可读性、健壮性、髙效率和低存储量等特征。

程序员在设计算法的过程中，除了要求算法能够准确地给出问题的答案外，还需要程序员能够尽可能地优化解决问题的方法，力求最大限度地降低算法的复杂度，将算法的运行时间降至最少。虽然条条大路通罗马，但是每一条道路耗费的代价都一样吗？每一条道路到达罗马的时间能够一样吗？显然不是，那么，在算法设计中，如何衡量一个算法的优劣？如何衡量程序员技术水平的高低？要回答这个问题，可以首先思考另一个问题，对于企业而言，需要什么样的人才？答案即花费最小的代价完成最多任务的人。所以，衡量算法优劣时，首要看的就是功能是否正常，其次看的就是其是否花费了更低的代价，即所谓的算法的复杂度。而算法的复杂度包括时间复杂度与空间复杂度，其中，时间复杂度用于度量算法执行的时间长短，空间复杂度用于度量算法的执行所需额外存储空间的大小，它们是衡量一个算法优劣的标准。下面将详细讨论如何分析一个算法的时间与空间复杂度。