算法学习：算法C语言实现 第二章 算法分析的原理

前言

第二章内容主要是使用数学方法对算法进行描述和分析。但是笔者只是粗浅的学习算法的应用，并没有搞研究的欲望，所以这章就记几个概念水过去算了。

算法分析的原理

算法及其分析常常纠缠在一起，学习算法分析的基本方法可以做到：

• 说明这个过程。
• 在某个地方描述所用的数学约定。
• 为讨论高级技术问题提供基础。
• 当比较算法时，对得出的科学基本结论进行正确评价。

实现和经验分析

表示算法的高效手段是使用实际的程序设计语言构造程序。这本书使用C语言描述，但是把C语言换成其它语言是很轻松的事。

如果一个算法是一个大系统的一部分实现，那么将使用抽象数据类型或类似的机制（C primer plus对此进行了一些讲解）。书中的算法只是一种描述，在实际应用中要考虑更多因素并使用更保守的设计风格：要对错误进行检查报告；要使程序修改更容易；要便于其他程序员理解；要对系统其他部分的接口良好；要能够方便移植到其他系统。

理解算法性能第一步就是经验分析：直接看哪个算法所用时间长。如果时间相差很大，经验分析能够节省很多时间，但是如果等待程序运行要花费数小时，那么就不如使用数学方法分析了。

选择算法时最常见的错误是忽视了算法性能。快速的算法比暴力解法更复杂，但是开发者宁愿牺牲算法性能也不愿意优化。第二个错误是过度关注算法性能，如果一个程序本身耗时短且不常用，就没必要花费太大精力去优化。

算法分析

对算法进行数学分析的目的：

• 比较同一任务的不同算法。
• 预测算法在新环境下的性能。
• 设置算法中的参数值。

算法分析第一步是明确算法的抽象操作。算法分析要求分离出抽象操作的代码块所需时间和抽象操作执行次数，使得对算法的比较不依赖与特定实现和特定计算机。

第二步是对算法的输入建立模型。分析时通常考虑两种方法：一是假设输入是随机的从而研究平均情况下的性能；二是寻求伪输入从而研究最坏情况下的性能。这两种情况都是理想状态，实际情况下很少见，但是这些分析可以为通常情况的性能提供信息。

函数的增长

大多数算法主要参数为N，其对算法运行时间影响最大。N是对所考虑问题的规模的抽象度量。算法运行时间一般会和这些函数成正比：1、logN、N、NlogN、N^2、N^3、2^N等等。有时还会在某些暴力算法中出现N!。

大O符号

分析算法时，大O符号可以使我们省略细节。大O符号有三个作用：

• 限制忽略数学公式中的低阶项时产生的误差。
• 限制由于忽略对程序总运行时间贡献较小的某些部分时产生的错误。
• 允许我们按照算法总运行时间的上界对算法进行分类。

大O符号允许我们在操作近似数学表达式时，只记得首项而忽略其它低阶项。我们称含有大O项的公式为渐近表达式。

基本递归方程

许多算法都基于递归分解原理，把大问题分解成子问题然后利用子问题的解求解原问题。这节介绍了几个算法的数学推导，这里直接记个结论：

• 如果程序的循环通过输入每次减少一项，则运行次数约为(N^2)/2。
• 如果程序每次使输入减少一半，则运行次数约为lgN。
• 如果程序每次使输入减少一半但是要检查输入的每一项，则运行次数约为2N。
• 如果程序把输入分成两半，但是在划分之前、划分之中、划分之后需要线性遍历输入，则运行次数约为NlogN。
• 如果程序把输入分成两半，然后做一些需要常量时间的其他工作，则运行次数约为2N。

算法分析示例

具备一些基本知识后，考虑两个基本的搜索算法：顺序搜索(sequential search)和二分搜索(binary search)。为了简化描述，假设讨论对象都是整数，并且打包为一个操作在数组上的C函数。

顺序搜索算法

这个函数从检查数value是否在事先存储的数集nums[first],nums[first+1],……,nums[last]中。从第一个元素开始按顺序比较每个元素，如果到达末尾没有找到则返回-1，否则返回这个数所在位置的数组下标。

int search(int nums[],int value,int first,int last)
{
  int index;
  for(index=first;index<=last;index++)
  {
    if(value==nums[index])
      return index;
  }
  return -1;
}

顺序搜索对于每次不成功的搜索需要检查N个数，对成功搜索平均需要检查约N/2个数。

假如使表中数据有序，则可以加快不成功搜索时的顺序搜索时间。在有序表中，当找到一个大于value的数时可以立即停止搜索，这种改变使得每次不成功搜索平均需要检查N/2个数。

二分搜索算法

在数据有序的情况下，二分搜索比顺序搜索更高效。通过把value和表中间位置的数字比较，可以去掉表中一半的数。

int search(int nums[],int value,int first,int last)
{
  while(last>=1)
  {
    int mid=(first+last);
    if(value==nums[mid])
      return mid;
    if(value<nums[mid])
      last=mid-1;
    else first=mid+1;
  }
  return -1
}

二分搜索至多检查[lgN]+1个数。

保证、预测及局限性

研究算法的最坏情况下的性能很有意义，因为这样可以对程序的运行时间做出保证。但是进行最坏情况下的分析存在一些困难，比如某些算法在最坏情况和一般情况之间存在很大差距，而且对于某些问题，在最坏情况下性能较好的算法可能比其他算法复杂的多。

研究算法的平均情况下性能也很有意义，因为这样可以使我们预测程序的运行时间。但是平均情况分析同样存在困难，比如我们不能保证实际输入是随机的，而且对于某些问题，分析平均情况性能需要深奥的数学知识。

总结

这章内容主要是使用数学方法对算法性能进行分析，稍微粗浅地记了几个结论，因为笔者学习这本书的主要目的是算法的应用，没有太多时间对理论进行深入。