2015年初级软考辅导:算法分析基础学习
发布时间：2010/3/13 14:40:27 来源：城市学习网 编辑：MOON
在计算机解决问题的过程中，数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。算法与数据结构的好坏直接相关，一种数据结构的优劣是由实现其各种运算的算法体现的。对数据结构的分析实质上也表现为对实现其多种运算的算法分析。算法分析是一个复杂的问题，它首先涉及到优劣准则的确定。判断一个算法的优劣主要有以下几个标准：
(1)正确性。要求算法能够正确地执行规定的功能。这是最重要也是最基本的准则;
(2)可使用性。算法应当是可读的，即可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的;
(3)健壮性。要求算法具有很好的容错性，即提供例外处理，能够对不合理的数据进行检查，不会经常出现异常中断或死机现象;
(4)效率。算法的效率主要指算法执行时计算机资源的消耗，包括存储和运行时问的开销，前者叫做算法的空间代价，后者叫做算法的时间代价。
时间代价是常用的评价指标，往往用时间复杂度来衡量。当一个算法转换成程序并在计算机上执行时，其运行所需要的时间总是取决于下列因素：
硬件的速度。CPu速度和存取数据的速度越快，则程序的执行时间越短;
所选用的程序设计语言。程序设计语言的级别越高，其执行效率就越低。比如汇编语言程序的执行效率往往要高于高级算法语言;
编译程序所生成目标代码的质量。对于代码优化较好的编译程序，其所生成的程序质量较高。比如，代码效率优化过的c++语言程序比未经过优化的代码效率要高;
问题的规模。很显然，大规模的问题求解过程比小规模的问题更耗费时间。
显然，在各种因素都不能确定的情况下，很难比较算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模，或者说它是问题规模的函数。另一方面，要全面地评价一个算法的优劣，不仅要考虑时间的耗费，还要考虑算法对存储器的耗费。特别是对于大规模问题，对空间耗费的分析是必不可少的。因此，分别有基于时间和空间的算法分析，即算法的时间复杂度分析和空间复杂度分析。
