本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第1章，第1.5节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.5算法与算法分析

算法与程序设计和数据结构密切相关。简单地说，算法是解决问题的策略、规则、方法。算法的具体描述形式很多，但计算机程序是对算法的一种精确描述，而且可在计算机上运行。数据结构的操作的实现方法就是一个算法问题，但该问题是针对数据结构的，是在给定的数据结构上进行的。下面从算法的特性、算法描述、算法性能分析与度量等方面对算法进行介绍。

1.5.1算法

算法(algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列。其中，每个指令表示一个或多个操作。一个算法必须满足以下五个重要特性。
1)有穷性。对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成。
2)确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
3)可行性。算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现。
4)有输入。输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上输入已被嵌入算法之中。
5)有输出。它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
算法与程序是两个不同的概念，两者之间既有联系又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不被破坏，它就永远不会停止。即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机中的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。
算法与数据结构是相辅相成的。解决某一特定类型的问题的算法可以选择不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

1.5.2算法设计的原则

要设计一个好的算法，通常应考虑达到以下目标。
1)正确性。首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：第1层是程序中不含语法错误，第2层是程序对于几组输入数据能够得出满足要求的结果，第3层是程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果，第4层是程序对于一切合法的输入数据都能得出满足要求的结果。通常以第3层意义的正确性作为衡量一个算法是否合格的标准。达到第4层意义的正确极为困难，因为对所有输入数据进行验证不现实。
2)可读性。算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。
3)健壮性。当输入的数据非法时，算法应当恰当地作出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4)高效率与低存储量需求。通常，效率指的是算法执行时间。对于同一个问题的多个算法，执行时间短的算法效率高。存储量指的是算法执行过程中所需的最大存储空间。这两者都与问题的规模有关。例如，求100个数的平均数和求10 000个数的平均数所花的执行时间和运行空间有一定的差别。

1.5.3算法效率的衡量方法和准则

算法执行时间需通过依据算法编制的程序在计算机上运行时所耗的时间来度量。通常有以下两种衡量算法效率的方法。
1)事后统计法。通过计算机内部的计时功能，求得算法的执行时间，从而衡量算法的效率。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间依赖于计算机的软、硬件等环境因素，有时容易掩盖算法本身的优劣。
2)事前分析估算法。依据算法编制的程序在计算机上执行时，其运行时间取决于下列因素：
算法选用的策略。
问题的规模。
编写程序的语言。
编译程序产生的机器代码的质量。
计算机执行指令的速度。
显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。因此，使用绝对时间单位衡量算法的效率是不合适的。撇开与计算机软、硬件环境有关的因素，可认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模(通常用整数量n表示)，或者说，它是问题规模的函数。
定义如果存在两个正常数c和n0使得对任意n≥n0有T(n)≤c*f（n），则T(n)=O(f(n))。
假如随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则记作T(n)=O(f(n))，称T(n)为算法的(渐近)时间复杂度。
如何估算算法的时间复杂度？通常从算法中选取一种对于所研究的问题来说是基本操作的原操作（指固有数据类型的操作），以该基本操作在算法中重复执行的次数(也称语句的频度)作为算法运行时间的衡量准则。
例如，在下列程序段中：

for(i=0;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=j;k++)
x=x+2;

基本操作“x=x+2”语句的频度为(n+1)*(1+2+…+n)=n(n+1)(n+1)/2，因此这个程序段的时间复杂度为O(n3)。
有些情况下，算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。例如，在下列起泡排序算法中：

void bubble_sort(int a［］,int n){//将a中整数序列重新排列成自小至大有序的整数序列

int i,j,temp,change;
for(i=n-1,change=1;i>0 && change;--i){
change=0;//change为元素进行交换的标志
for(j=0;j<i;++j)
if(a［j］>a［j+1］){
temp=a［j］;
a［j］=a［j+1］;
a［j+1］=temp;
change=1;
}
}
}//bubble_sort

“交换序列中相邻两个整数”为基本操作。当a中序列自小到大有序时，基本操作的执行次数为0；当初始序列自大到小有序时，基本操作的执行次数为n(n－1)/2。对于这类算法时间复杂度的分析，一般取其平均时间复杂度。但当无法计算平均时间复杂度时，则取其最坏情况下的时间复杂度。于是，可得上述算法的时间复杂度为O(n2)。

1.5.4算法的存储空间需求

空间复杂度作为算法所需存储空间的量度，记作S(n)=O(g(n))，其中n为问题的规模，它表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算机所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。