3.1　算法的概念

程序：程序实质是完成既定任务的指令序列。而编写程序的工具是语言。

    程序 = 数据结构 + 算法 + 程序设计方法 + 语言工具环境

算法是灵魂，是问题求解过程中的精确描述；数据结构是加工对象；语言是工具；编程需要采用合适的方法。

算法是对特定问题求解步骤的一种描述，它是指令的有限序，其中每一条指令表示一个或多个操作。算法解决的是“做什么”和“怎么做”的问题，程序中的操作语句就是算法的体现。

计算机算法可分为两大类：数值运算算法、非数值运算算法。

数值运算算法：数值运算的目的是求数值解，如：求方程的根、函数的定积分等。

非数值运算算法：应用十分广泛，如：图书检索、人事管理、行车调度管理、排序算法等。

3.1.1　算法的特性

算法在解决问题时具有以下特性：

1．有穷性

对任何合法的输入值，算法中每个步骤由计算机执行的次数及时间都是有限的。

2．确定性

算法中每个步骤含义明确，无二义性。在任何条件下，相同的输入，必有相同的输出。

3．有零个或多个输入

在计算机上实现的算法是用来处理数据对象的，在大多数情况下这些数据对象需要通过输入来得到。

输入是指在执行算法时需要从外界来获取若干必要的初始量等信息。

例如：

    z=x+y;

此时需要用户给定变量x和变量y的值以计算变量z的值。

又例如：

    printf("My first programm");

此时只是需要输出一段字符串，不需要用户输入任何数据，此为零输入。

4．有一个或多个输出

算法的最终目的就是为了求解，通过输出的方式来将求出的结果显式出来。若是一个程序在执行结束后没有返回任何信息，那么此程序就没有执行的价值。

5．有效性

算法中描述的操作都可通过有限次的基本运算来实现。

例如：

    int x=2,y=0;
    z=x/y;

此时，“z=x/y”便为一个无效语句，因为使用0作为分母是没有意义的。

3.1.2　衡量算法的“好”与“坏”

由于针对一个问题可能会用不同的算法去解决，不同的算法思路不同，有的执行速度很慢，效率低；有的执行速度很快，效率自然会很高。这样也就出现了算法的好坏之分，如何衡量一个算法的好坏，通常要从以下几个方面来分析。

1．正确性

设计的算法应当满足具有输入、输出和加工处理等明确的无歧义性的描述的具体问题的需求。验证正确性通常有4个层次：

①　程序不含语法错误。

②　程序对于几组输入数据能够得出满足规格说明要求的结果。

③　程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

④　程序对于一切合法的输入数据能够得出满足规格说明要求的结果。一般情况至少通过第③层的验证。

2．可读性

算法主要是为了阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，难懂的程序易于隐藏较多错误，难以调试和修改。

3．健壮性

当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

4．时间复杂度与空间复杂度

主要指算法执行时的最长时间与所需的最大存储空间。

时间复杂度简单地说就是算法运行所需要的时间。影响一个算法的时间复杂度主要有以下因素：

（1）问题的规模大小。例如，求解10以内自然数之和与求解1000以内自然数之和所花费的时间是不同的。

（2）源程序的编译功能强弱以及经过编译所产生的机器代码质量的优劣。

（3）根据计算机的系统硬件所决定的机器执行一条目标指令所需要的时间。

（4）程序中语句所执行的次数。

（5）使用不同的计算机语言所实现的效率。

程序中语句的执行次数。这个因素与算法本身有直接关系，一个好的算法应该使程序中语句执行次数尽量少。

不同的算法具有不同的时间复杂度，当一个程序较小时，就感觉不到时间复杂度的重要性，当一个程序特别大时，便会察觉到时间复杂度实际上是十分重要的，所以如何写出更高速的算法一直是算法不断改进的目标。

空间复杂度是指算法运行所需的存储空间的多少。一个算法在计算机存储器上所占用的存储空间包括算法本身所占的存储空间、算法的输入／输出数据所占的存储空间以及算法运行过程中所占用的临时存储空间。随着计算机硬件的发展，空间复杂度已经显得不再那么重要了，但在编程时也应该注意。