算法是计算机科学和技术中一个十分重要的概念。程序设计的本质在Niklaus Wirth所著的《算法+数据结构=程序》这本书的书名中被揭示了出来。Niklaus Wirth的这个“公式”指出了计算机程序设计的双重特性：一个程序由描述如何用计算机处理信息的算法与在计算机中怎样组织信息的数据结构组成。算法与数据结构是互相依赖、互相联系的，不能将它们分开独立研究。也就是说，在某一个方面做出的决定常常会影响到另一个方面。
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法有以下5个重要特征：
· 有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
· 确定性。算法中每一条指令必须有确切的含义，不会产生二义性。
· 可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算的有限次执行来实现。
· 输入性。一个算法有零个或多个输入值。
· 输出性。一个算法有一个或多个输出值。
【例1-2】求n个数的最大值问题，给出示意算法如下：
max=0;
for(i=0;i<=n;i++)
{
scanf("%f",&x);
if (x>max) max=x;
}
该算法是否正确？
解：求最大值的算法无语法错误；当输入n个数全为正数时，结果也对，但输入n个数全为负数时，求得的最大值为0，显然这个结果不对，由这个简单的例子可以说明算法正确性的内涵。
【例1-3】考虑下列两段描述：
（1）void exam1() （2）void exam2()
{ {
n=2; y=0;
while(n%2==0) x=5/y;
n=n+2; printf("%d,%d\n",x,y);
printf("%d\n",n); }
}
这两段描述均不能满足算法的特征，试问它们违反了哪些特征？
解：（1）是一个死循环，违反了算法的有穷性特征。（2）包含除数为0的错误，违反了算法的可行性特征。
下面总结常用的描述算法的C语言语句。
（1）输入语句
scanf(格式控制字符串,输入项表);
（2）输出语句
printf(格式控制字符串,输出项表);
（3）赋值语句
变量名=表达式;
（4）条件语句
if <条件> <语句>;
或者
if <条件> <语句1> else <语句2>;
（5）循环语句
· while循环语句
while 表达式
循环体语句;
· do…while循环语句
do
循环体语句;
while 表达式;
· for循环语句
for(赋初值表达式1;条件表达式2;步长表达式3)
循环体语句;
（6）返回语句
return(返回表达式);
（7）定义函数语句
函数返回值类型 函数名(类型名 形参1,类型名 形参2,…)
{
说明部分;
函数语句部分;
}
（8）调用函数语句
函数名(实参1,实参2,…)
C++语言中，在函数调用时实参和形参的参数传递分为传值和传引用（引用符号为“&”）两种方式。
注意：C语言不支持引用，只有C++语言支持引用，本书除了采用C++中的引用描述算法外，其他都采用C语言语法。
传值方式是单向的值传递。例如，有一个函数fun1(x,y)（其中x和y为值形参），在调用fun1(a,b)（其中a和b为实参）时，将a的值传给x，b的值传给y，然后执行函数体语句，执行完函数后，x、y的值不会回传给a、b。
传引用方式是双向的值传递。例如，有一个函数fun2(x,y)（其中x和y为引用形参），在调用fun2(a,b)（其中a和b为实参）时，将a的值传给x，b的值传给y，然后执行函数体语句，执行完函数后x、y的值分别回传给a、b。
例如，有如下程序：
#include <stdio.h>
void fun1(int x,int y) /*参数传递的传值方式*/
{
y=(x<0)?-x:x;
}
void fun2(int x,int &y) /*参数传递的传引用方式*/
{
y=(x<0)?-x:x;
}
void main()
{
int a,b;
a=-2;b=0;
fun1(a,b); /*b的值不会发生改变*/
printf("fun1:b=%d\n",b);
a=-2;b=0;
fun2(a,b); /*b的值发生改变*/
printf("fun2:b=%d\n",b);
}
其中，fun1(x,y)、fun2(x,y)的功能都是计算y=|x|，fun1中形参y使用传值方式，fun2中形参y使用传引用方式。也就是说，执行fun1(a,b)时，b实参的值不会改变，而执行fun2(a,b)时，b实参的值可能发生改变。程序执行结果如下：
fun1:b=0
fun2:b=2
为此，在设计算法（通常设计成C/C++函数）时，若某个形参需要将计算的值回传给对应的实参，则需将其设计为引用传递参数的方式，否则不必使用引用方式。
评价一个好的算法有以下几个标准。
（1）正确性（Correctness）。算法应满足具体问题的需求。算法的正确性是指对于一切合法的输入数据，该算法经过有限时间的运行都能得到正确的结果。一个算法包括两个方面的内容，一是解决问题的方法；二是实现这一方法的一系列指令。
“正确性”的含义一般分为4个层次：①算法不含语法错误；②算法对于正确的输入数据都能得到符合规格说明要求的结果；③算法对于精心设计的测试用例中的输入数据也能得到符合规格说明要求的结果；④算法对于一切合法的输入数据都能得到符合规格说明要求的结果。显然，要达到第4层意义的标准极为困难，一般来说，以第3层意义的正确性作为衡量算法是否合格的标准。
（2）可读性（Readability）。算法应该易于阅读者对程序的理解。晦涩难懂的算法不但容易隐藏较多的错误，而且也增加了人们在阅读、理解、修改、调试和重用等方面的困难和不便。
（3）健壮性（Robustness）。算法应具有容错处理。当输入非法数据时，算法应对其做出反应，而不是产生莫名其妙的输出结果。一个健壮性好的算法能对输入数据进行语法检验，提出修改错误的具体建议，并提供重新输入数据的机会，既不会简单地拒绝输入，也不会放过错误。
（4）时间效率与存储量需求。效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。对于一个问题，如果存在多个可行的算法，则执行时间较短的算法其效率较高。一般地，算法的时间效率与存储量需求都与问题的规模有关，它们是度量算法的两个主要指标。
除此之外，一个好的算法还应具有灵活性、可重用性和自适应性等。
算法分析的两个主要方面是算法的时间复杂度和空间复杂度，其目的不是分析算法是否正确或是否容易阅读，而是考察算法的时间和空间效率，以求改进算法或对不同算法进行比较。一般情况下，鉴于运算空间（内存）较为充足，通常把算法的时间复杂度作为分析的重点。
算法的执行时间主要与问题规模有关。问题规模是一个和输入有关的量。例如，数组的元素个数、矩阵的阶数等。所谓一个语句的频度，即指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作T(n)，它是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，T(n)的数量级称为渐近时间复杂度，简称为时间复杂度，记作T(n)= O(f(n))。
上述表达式中“O”的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f (n)是定义在正整数集合上的两个函数，则存在正的常数C和n0，使得当n≥n0时，总是满足0≤T(n)≤C· f (n)。但是应总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
另外，由于算法的时间复杂度主要分析T(n)的数量级，而算法中基本运算的频度与T(n)同数量级，所以通常采用算法中基本运算的频度来分析算法的时间复杂度，被视为算法基本运算的一般是最深层循环内的语句。
用数量级形式O(f (n))表示算法执行时间T(n)的时候，函数f (n)通常取较简单的形式，如1，log2n，n，nlog2n，n2，n3，2n等。在n较大的情况下，常见的时间复杂度之间存在下列关系：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
【例1-4】计算下面求累加和程序段的时间复杂度。
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum++;
其中，第一条语句执行1次。第二条语句的循环变量i要增加到n，故执行n次。第三条语句作为第二条语句的循环体内的语句，因此应执行n2次。而第四条语句作为第三条语句的循环体语句也要执行n2次。所以，该程序段所有语句执行的次数为：
T(n) = 2 n2 + n +1
故其数据复杂度为：
T(n) = O(n2)
【例1-5】计算下列交换i和j内容程序段的时间复杂度。
temp=i;
i=j;
j=temp;
以上3条语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶，即T(n)=O(1)。
空间复杂度是算法所需存储空间的度量，记作：
S(n)=O(f (n))
其中n为问题的规模（或大小）。
通常，执行一个算法程序除了需要存储空间存放本身所用的指令、常数、变量和输出数据外，还需要一些辅助空间用于对数据进行处理及存储处理过程中的中间信息。若输入数据所占的空间只取决于问题本身而与算法无关，则只需要分析除了输入和程序之外的辅助空间需求。算法的空间复杂度通常指的就是这种辅助空间需求的大小。
实践中，算法的空间复杂度和时间复杂度是彼此相关的两个方面。有时要想空间比较节约，往往时间消耗就大，反之，时间开销小，常常得用空间资源的消耗来换取，如链表结构中节点的指针域，这种额外空间需求称为“结构性开销”。从理论上来讲，这种结构性开销应该尽可能小，而访问的路径又应该尽可能多且有效。这种互相矛盾的目标之间的权衡也正是算法和数据结构研究的乐趣和魅力所在。