一、算法分析

  本章讨论的主题是：

•   如何估计一个程序需要的时间。

•   如何将一个程序的运行时间从天或年降低到不足一年。

•   粗心地使用递归的后果。

•   用于将一个数自乘得到其幂以及计算两个数的最大公因数的非常为有效的算法。

 1.1 数学基础

 定义1 .1  如果存在正常数c和n0使得当N≥n0时T(N)≤cf(N)，则记为T(N)=Ο(f(N))。

 定义1 .2  如果存在正常数c和n0使得当N≥n0时T(N)≥cg(N)，则记为T(N)=Ω(g(N))。

 定义1 .3  T(N)=Θ(h(N))当且仅当T(N)=Ο(h(N))和T(N)=Ω(h(N))。

 定义1 .4  如果对所有的常数c存在n0使得当N>n0时T(N)<cp(N)，则记为T(N)=ο(p(N))。非正式定义为：如果T(N)=Ο(p(N))且T(N)≠Θ(p(N))，则T(N)=ο(p(N))。

  这些定义的目的是要在函数间建立一种相对的级别。我们将比较它们的相对增长率（relative rates of growth）。 虽然N较小时，1000N要比N^2大，但N^2以更快的速度增长，因此N^2最终将更大，如T(N)=1000N，f(N)=N^2，在n0=1000而c=1，或者n0=10而c=100时，T(N)=f(N)。因此，我们可以说1000N=Ο(N^2)（N的平方级）。这种记法称为大Ο记法。

  如果我们用传统的不等式来比较增长率，那么第一个定义式说T(N)的增长率小于等于(≤)f(N)的增长率。第二个定义式T(N)=Ω(g(N))是说T(N)的增长率大于等于(≥)g(N)的增长率。第三个定义式T(N)=Θ(h(N))是说T(N)的增长率等于(=)h(N)的增长率。最后一个定义式T(N)=ο(p(N))是说T(N)的增长率小于(<)p(N)的增长率。它不同于大Ο，因为大Ο包含增长率相同这种可能性。

  直观上来讲，如果g(N)=2N^2，那么g(N)=Ο(N^4),g(N)=Ο(N^3)和g(N)=Ο(N^2),从技术上讲都是成立的，但最后一个选择是最好的。写法上g(N)=Ο(N^2)g(N)=Ο(N^2)g(N)=Ο(N^2)g(N)=g(N)=

Ο(N^2)g(N)=Θ(N^2)不仅表示g(N)=g(N)=Ο(N^2)，而且还表示结果尽可能地好(严格)。

    法则1：如果T1(N)=Ο(f(N))和T2(N)=Ο(g(N))，那么

  （a）T1(N)+T2(N)=Ο(f(N)+g(N))（直观的非正式表达式为max(Ο(f(N),g(N)))）

  （b）T1(N)T2(N)=Ο(f(N)g(N))

     法则2：如果T(N)是一个k次多项式，则T(N)=Θ(Ο(N^k))。

 

     法则3：对任意常数k，(logN)^k=Ο(N)。它告诉我们对数增长得非常缓慢。

   这些信息足以按照增长率来对大部分常见的函数进行分类，见下图：

图1-1  典型的增长率（其中NlogN为线性对数）

  需注意几点：

  首先，将常数或低阶项放进大Ο是非常不好的习惯。不要说T(N)=Ο(2N^2)或者T(N)=Ο(N^2+N)。这两种情况下，正确的形式应该是T(N)=Ο(N^2)。在大Ο的任何分析中，各种简化都有可能发生。低阶项一般被忽略，常数也可以被丢弃。此时，要求的精度是很低的。

  其次，我们总能够通过计算极限limN->∞f(N)/g(N)来确定两个函数f(N)和g(N)的相对增长率，必要时可以使用罗必达法则。该极限可以有四种可能值：

• 极限是0：这意味着f(N)=ο(g(N))。

• 极限是c≠0：这意味着f(N)=Θ(g(N))。

• 极限是∞：这意味着g(N)=ο(f(N))。

• 极限摆动：这意味二者无关（很少发生这种情况，这里不会遇到）。

 1.2 模型

  为了在形式的框架中分析算法，我们需要一个计算模型。我们的模型基本上是一台标准的计算机，在机器中指令被顺序执行，该模型有一个简单指令系统，如加法、乘法、比较和赋值等。但不同于实际计算机的是，该模型做任何一件简单的工作都恰好花费一个时间单位。为了合理起见，我们将假设我们的模型如同一台现代计算机那样有定长（比如32位）的整数并且不存在诸如矩阵求逆或排序运算，它们显然不能在一个时间单位完成。我们还假设模型机有无限的内存。

  显然这个模型存在缺点。现实生活中不是所有的运算都恰好花费相同的时间。还有无线内存就不用担心缺页，但这可能是个实际问题，特别对于高效的算法。

 1.3 要分析的问题

  要分析的最重要的资源一般来说就是运行时间，有几个因素影响着程序的运行时间。有些因素（如所使用的编译器和计算机）明显超出了任何理论的范畴，虽然重要，但我们这里不能处理。剩下的主要因素则是所使用的算法以及对该算法的输入。

  平均情况常常反映典型的结果。所得到的实际上是算法的界，而不是程序的界，程序语言的细节几乎步影响大Ο的结果。一般的，无特别说明。则需要的量就是最坏情况的运行时间，一是因为它对所有的输出提供了一个界，二是因为平均情况的界计算起来通常要困难得多。

     最大的子序列和问题  给定整数A1，A2，…，AN (可能有负数)，求的最大值。

  这个问题有很多算法，而这些算法性能差距又很大。下面给出四种算法在某台计算机上的运行时间，如下图：

图1-2 对于计算最大子序列和的几种算法的运行时间（s）

  图中有几个重要的情况值得注意。对于小输入算法瞬间完成，因此没有必要为小量输入的情况花费大量努力设计聪明的算法。另一方面，近来重写那些不再合理的基于小输入量假设而在五年前编写的程序确实存在巨大的市场。

  其次，图中图中给出的时间不包括输入数据所需的时间。对于很多高效算法，数据的读入一般是个瓶颈，只要数据输入，问题就可以迅速解决;而对于低效率的算法，它必然要耗费大量的计算机资源。图1-3显示了四种算法运行时间的增长率，图1-4显示对于更大值的性能。该图戏剧性的描述处，即使是适度大小的输入量，低效的算法依然无用。

图1-3 各种计算最大子序列和的算法图（横坐标为N，纵坐标为时间）

图1-4 各种计算最大子序列和的算法图（横坐标为N，纵坐标为时间）

 1.4 运行时间计算

  为了简化分析，我们将用以下约定：不存在特定的时间单位。因此，我们将抛弃常数项系数和低阶项，只是计算大Ο运行时间。程序可以提前结束，但不能拖后。

  1.4.1 一个简单的例子

  下面是计算的一个简单的程序片段：

int sum(int n){  int partialSum;  partialSum = 0;  for(int i = 1; i <= n; i++)    partialSum += i*i*i;  return partialSum;}

  声明不计算时间。第三行和第六行各占一个时间单位，第五行每执行一次占用4个时间（两个乘法、一次加法和一次赋值），而执行N次共占用4N个时间单位。第五行初始化占1个时间单位，所有测试i<=N为N+1个时间单位，而所有的自增运算N个时间单位，共2N+2。我们忽略使用方法和返回值的开销，得到总量为6N-4。因此，我们说该方法是Ο(N).

  我们可以采用捷径而并不影响最后的结果。例如，第6行（每次执行时）显然是Ο(1)语句，因此计算它究竟是2个、3个还是4个时间单位是愚蠢的。第三行与for循环相比显然是不重要的，所以在这里花费时间页是不明智的。这使得我们得到以下若干法则。

 

  1.4.2 一般的法则

  法则1：for循环 一个for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数。

  法则2：嵌套循环 从里向外分析这些循环，在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。

  法则3：顺序语句 将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）。

  法则4：if/else语句 对于程序片

if(condition)  s1else  s2

  一个if/else语句的运行时间从不超过判断再加上s1和s2中运行时间较长者的总的运行时间。

  分析的基本策略是从内部（或最深层部分）向外扩展工作。如果有方法调用，那么这些调用要首先分析。如果有递归过程，那么存在几种情况：

  若递归实际上可以转化为for循环，那么通常是很简单的。例如下面的例子实际就是一个循环，其运行时间为Ο(N)：

long factorial(int n){  if(n <= 1)    return 1;  else    return n * factorial(n - 1);}

  这个例子对递归使用得并不恰当，正常使用递归，将其转换成一个简单的循环结构是相当困难的。这种情况下，涉及求解一个递推关系。如以下程序，实际它对递归的使用效率极其低下：

long fib(int n){  if(n <= 1)    return 1;  else    return fib(n - 1) + fib(n - 2); }

  初看起来，该程序似乎对递归的使用非常聪明。但当N赋值在40左右，这个程序的效率低得吓人。下面是分析，令T（N）为函数fib(n)的运行时间。当N=0或者N=1，则运行时间是某个常数值，我们可以说T（0）=T（1）=1。若N>=2，执行时间是第三行的常数时间加第五行上的时间，即T（N-1）+T（N-2）+2，其中2是指第三行加上第五行的加法时间。于是N>=2 的时间公式为：T（N）=T（N-1）+T（N-2）+2。可以证明这个程序的运行时间以指数增长。这大致是最坏的情况。编写递归程序有四条基本法则：

1. 基准情形。必须总是有某些基准情形不用递归能求解。

2. 不断推进。对于那些需要递归求解的情形，递归调用必须总能够朝着基准情形的方向推进。

3. 设计法则。假设所有的递归调用都能运行。

4. 合成效益法则（compound interest rule）。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作。

  这个程序明显违反了第四条合成效益法则。下面是递归出色的应用。

 

  1.4.3 最大子序列求和问题

  下面是四个算法来求解最大子序列和的问题。

  第一个算法只是穷举式地尝试所有的可能，本算法不计算实际的子序列：实际计算还要添加一些额外的代码

int maxSubSum1(const vector
    
      &a){  int maxSum = 0;    for(int i = 0; i < a.size(); i++)    for(int j = i;j < a.size(); j++)      {        int thisSum = 0;                for(int x = i; k <= j; k++)          thisSum += a[k];                  if(thisSum > maxSum)          maxSum = thisSum;               }  return maxSum;}
    

  第五行上的第一个循环大小为N。第二个循环大小为N-1，但也可能是N。我们必须假设最坏情况N。第三个循环大小为j-i+1，我们也要假设它为N。而第11行为Ο(1)，所以总数为Ο(1*N*N*N)=Ο(N^3).

  第二个算法进行了改进,复杂度显然是Ο(N^2).

int maxSubSum2(const vector
    
      &a){  int maxSum = 0;    for(int i = 0; i < a.size(); i++)  {      int  thisSum = 0;      for(int j = i;j < a.size(); j++)      {        thisSum += a[ j ];                          if(thisSum > maxSum)          maxSum = thisSum;           }  return maxSum;}
    

  第三个算法是一个递归和相对复杂的Ο(NlogN)解法。该方法采用一种“分治”（divide-and-conquer）策略。

int maxSumRec(const vector
    
      &a, int left, int right){  if(left == right)  //base case    if(a[left] > 0)      return a[left];    else      return 0;        int center = (left + right) / 2;  int maxLeftSum = maxSumRec(a, left, center);  int maxRightSum = maxSumRec(a, center - 1, right);    int maxLeftBorderSum = 0;  int leftBorderSum = 0;  for(int i = center;i >= left; i--)  {    leftBorderSum += a[ i ];    if(leftBorderSum > maxLeftBorderSum)      maxLeftBorderSum = leftBorderSum;  }    int maxRightBorderSum = 0;  int rightBorderSum = 0;  for(int j = center;j <= right; j++)  {    rightBorderSum += a[ i ];    if(rightBorderSum > maxRightBorderSum)      maxRightBorderSum = rightBorderSum;  }    return max3(maxLeftSum,maxRightSum, maxLeftBorderSum + maxRightBorderSum);  }int maxSubSum3(const vector
     
       &a){  return maxSumRec(a, 0, a.size() - 1);}
     
    

  可以得出程序的花费的方程组为：

                    T(N) = 1

               T(N) = 2T(N/2) + Ο(N)

  可得到若N=2^k，T(N)=N*(k+1)=NlogN + N=Ο(NlogN)。

  第四种方法比递归更简单且更有效，

int maxSubSum4(const vector
    
      &a){  int maxSum = 0;  int thisSum = 0;    for(int j = 0; j < a.size(); j++)  {    thisSum += a[ j ];        if(thisSum > maxSum)      maxSum = thisSum;    else if(thisSum < 0)      thisSum = 0;  }    return maxSum;}
    

  这个算法是许多聪明算法的典型：运行时间是明显的，但正确性则不明显。正确性需要费用精力来证明。这个方法附带的优点是它只对数据进行一次扫描，一旦数据被处理，就不需要被记忆。具有这种特性的算法叫做联机算法（on-line algorithm）。仅需要常量空间并以线性时间运行的联机算法几乎是完美的。

  1.4.4 运行时间中的对数

  分析算法最混乱的部分大概是集中在对数上。除了某些分治算法的Ο(NlogN)运行时间外，对数常出现的规律如下一般法则：如果一个算法用常数时间Ο(1)将问题的大小消减为其一部分（通常是1/2），那么该算法就是Ο(logN)。另外，如果使用常数时间只把问题减少一个常数数量（如1），那么这种算法就是Ο(N)。因为输入N个数就要耗费Ω(N)的时间，所以Ο(logN)这类问题都是假设已输入数据的前提下进行。

 

   1.4.4.1 二分搜索

   二分搜索（binary search）    给定一个整数X和整数A0，A1，…，AN-1，后者已经预先排序并在内存中，求下标i使得Ai=X，如果X不在数据中，则返回i=-1。

  明显的解法是从左到右扫描数据，其运行花费为线性时间。然而，没有用到该表已经排序的事实，这就使得该算法很可能不是最好的。而可以利用二分搜索程序,运行时间是Ο(logN)。

template 
    
     int binarySearch(const vector
     
       &a, const Comparable &x){  int low = 0;  int high = a.size() - 1;      while(low <= high)  {    int mid = (low + high) / 2;        if(a[ mid ] < x)      low = mid + 1;    else if(a[ mid ] > x)      high = mid + 1;    else      return mid;  /Found  }  return NOT_FOUND;  //NOT_FOUND is defined as -1}
     
    

 

   1.4.4.2 欧几里得算法

  第二个例子是计算最大公因数的欧几里得算法。下面是计算最大公因数ged(M,N)，假设M>=N（如果N>M，则循环的第一次迭代将它们互相交换）。

long ged(long m, long n){  while(n != 0)    {      long rem = m % n;      m = n;      n = rem;    }    return m;}

  定理1.1  如果M > N，则M mod N < M/2。

  证明：存在两种情况。如果N<=M/2，则由于余数小于N，故定理在这种情形下成立的。另外一种情况是N>M/2，但是此时M仅含有一个N从余数为M-N<M/2，定理得证。

 

 

   1.4.4.3 幂运算

  最后一个例子是处理一个整数的幂（它还是一个整数）。我们将用乘法的次数作为运行时间的度量。

long pow(long x, int n){  if(n == 0)    return 1;  if(n == 1)    return x;  if(isEven(n))    return pow(x*x, n / 2);  else    return pow(x*x, n / 2) * x;}

 

 

  1.4.5 检验你的分析

  例如下面的例子，计算两个随机选取、小于或者等于N的互异正整数的概率（当N增大时，结果将趋于6/π^2）。

double probRelPrime(int n){  int rel = 0;  int tot = 0;    for(int i = 1; i <= n; i++)    for(int j = i + 1; j <= n; j++)    {      tot++;      if(ged(i, j) == i)        rel++;    }      return (double) rel / tot;}

  验证一个程序是否有Ο(f(N))的一个技巧是对N的某个范围计算比值T(N)/f(N)（通常由2的倍数隔开），其中T(N)是凭经验观察到的时间。如果f(N)是运行时间的理想近似，那么算出的值收敛于一个正常数。下面是在一台计算机上实际观察得到的运行时间。

                                    图1-5  对上述例程的经验运行时间

 

  1.4.6 分析结果的准确性

  经验指出，有时分析结果会过大，这种情况需分析的更细。或者可能平均运行时间明显小于最坏情况，对于许多复杂算法，最坏情况可以通过某个不良输入得到，但在实践中一般估计过大。遗憾的是，一般平均情况的分析极其复杂，而最坏情况尽管过分悲观却是最好的已知分析结果。