对算法进行分析（1）

IT商界

PALADIN

　　从本期开始，笔者准备用两到三期的篇幅来和朋友们谈谈算法的分析以及问题的计算复杂性。由于这方面问题牵扯到很多数学概念，讲起来或者看起来都会比较晦涩和复杂，所以笔者将尝试在少讲数学公式的前提下尽可能地把问题讲解清楚。

　　怎样分析算法

　　首先，把会遇到的几个概念问题说一下。算法的分析是针对具体的算法，我们对算法的稳定性、算法的复杂性(包括算法的时间复杂性和空间复杂性)进行分析，并以此作为依据来比较算法间的优越性。

　　算法的稳定性主要研究的是算法对于运算误差是增加还是减小，是线性增加还是指数增加。而算法的时间复杂性主要研究的是算法在执行时的工作量多少的问题。通常，一个算法必须在有限步骤之后终止，即必须在有限时间内完成。当然对于在计算机上需要运行百万、千万年的算法，显然对我们是没有实际价值的。

　　至于算法的空间复杂性主要研究的是算法执行过程中占用内存空间的多少。例如前面我们做过的8个棋子的问题中，有的朋友用了一个8×8的二维数组来存放棋盘上的信息，而有的朋友就用了4个一维数组来存放信息，很明显这两种方法占用的内存空间的数量是不同的。

　　前面我们说到复杂性都是针对问题的一个具体算法而言的，是算法层的计算复杂性。关于问题的复杂性是指分析一个问题的所有算法，确定求解该问题复杂性下线(也可以认为是找最优算法)。对于问题的复杂性我们现在大体有两种大的划分，一是P问题(多项式界问题)、一是NP问题(非多项式界问题)。简单地说，P问题就是问题存在一个多项式界的算法(算法的时间复杂性可以用多项式表示)。NP问题就是还没有找到多项式界算法的问题。看到这里，你应该会有n个问号了，下面我们来谈谈具体的内容。

　　时间的复杂性

　　首先要讲的是算法的时间复杂性。比较算法优劣的很多场合往往就是只考虑算法的时间复杂性。首先我们来看一个问题：已知不重复且已经按从小到大排序好的M个整数的数组A[1..M]，现给定一个整数C，要求寻找一个下标I，使得A[I]=C；若找不到，返回一个0。

　　对于这个问题，我们可以考虑一个简单的办法，就是从头到尾扫描数组A。容易看出，在最坏的情况下，这个算法要检验A的所有M个分量(如果C刚好等于A[M]或是C大于A[M])。另外，我们还有一个算法就是择半比较的办法。就是首先用A的中间量A[M/2]与C比较，如果A[M/2]=C就已经找到，如果A[M/2]大于C，则C只能在A[1]到A[M/2-1]的范围内继续查找；如果A[M/2]小于C，则C只能在A[M/2+1]到A[M]的范围内继续查找。很明显这种算法在最坏情况下，检验的次数要少于前面的算法，因为每进行一步，搜索的范围就减少一半(感兴趣的朋友可以验证一下，第二种算法在最坏的情况下只要检验log2M+1个分量)。

　　对复杂性的描述

　　显而易见，不同算法的在解决同一个问题时的解决时间往往是不同的，而且有时是差别巨大的。但我们怎样来描述这些算法的时间复杂性呢？首先，我们要排除一些干扰因素。同样的程序在不同配置的机器上执行的时间是会不一样的，这应该很好理解。不同的编程语言环境实现同一个算法，运行的速度也是不一样的。JAVA比Delphi是要慢些，因为JAVA是解释执行的。另外，同样的算法在解决不同输入规模的情况下，运行的时间也会是不同的。这也很好理解，都是做矩阵的乘法，4×4的矩阵和8×8的矩阵的运算量就差很多。所以综上所述，我们在考虑算法的时间复杂性的时候要考虑机器、编程语言环境以及问题的具体实例等因素。

　　对于不同的问题输入，算法的执行情况是不一样的，用时也往往是不同的。为了更好地衡量算法的时间复杂性、比较算法的优劣，我们常考虑用一些极限条件下。算法的工作情况来作为评判标准，例如最好时间复杂性、最坏时间复杂性。另外有一种平均时间复杂性也是会被使用的，它是将所有可能输入情况的发生比例和相应的工作用时的乘积的累计。这里，我们只准备讨论算法的最坏时间复杂性。

　　在考虑算法时间复杂性的时候还有一条重要的原则，就是要选择合适的基本运算作为衡量标准，要忽略一些次要的细节问题，例如循环下标的计算、数组下标的计算、设置数据结构指针等“簿记”(bookkeeping)运算等。这样，分析算法的工作量，用直接计算所执行的基本运算次数就可以得到了。另外，我们要选择的基本运算，还要和算法执行的运算总次数大体上成比例。