算法和算法分析2

对于同一个问题，可以有许多不同的算法。究竟如何来评价这些算法的优劣程度呢？

算法分析的目的是看算法实际是否可行，并在同一问题存在多的算法时可进行性能上的比较，以便于从中挑选出比较优的算法。

• 一个好的算法首先是具备正确性，然后是健壮性、可读性，在这些方面都满足的情况下，主要考虑算法的效率，通过算法效率高低来评判不同算法的优劣程度。

• 算法效率以下两个方面来考虑：

  • 时间效率：指的是算法所耗费的时间。
  • 空间效率：指的是算法所占用的存储空间
  • 时间效率和空间效率有时候是矛盾的。

• 算法时间效率的度量

  • 算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量
  • 两种度量方法
    • 事后统计
      • 将算法实现，测算时间和空间开销。
      • 缺点：编写程序实现算法将花费较多的时间和精力；所的实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣
    • 事前分析
      • 对算法所消耗的资源的一种估算方法。

• 事前分析方法：

  • 一个算法的运行时间是指一个算法在是计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积。

    • 算法运行时间=一个简单操作所需的时间*简单操作次数

  • 也即算法中每条语句的执行时间之和

    • 算法运行时间=∑每条语句的执行次数*该语句执行一次所需的时间

    • 每条语句的执行次数（也叫语句频度），每条语句执行一次所需的时间是由机器本省软硬件环境决定的。

    • 例如：两个n*n矩阵相乘的算法可描述为：

      for(i=1;i<=n;++i)												// n+1次
        for(j=1;j<=n;++j){										// n(n+1)次
          c[i][j]=0;												  // n*n 次
        	for(k=0;k<n;++k)										// n*n*(n+1) 次
            c[i][j]=c[i][j]+a[i][j]*b[k][j];		// n*n*n
      	}
      

    • 我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：
      T(n)=

• 渐进时间复杂度

  • 为了便于比较不同算法的时间效率，我们仅比较它们的数量级
  • 若有某个辅助函数f(n)，使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称为f(n)是T(n)的同数量级函数。记作T(n)=f(n),称o(f(n))为算法渐进时间复杂度（O是数量级的符号），简称时间复杂度。