算法效率的质量与时间复杂度

beyes

算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：

(1)事后统计法
计算机内部都有计时功能，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。这种方法有两个缺陷：一个是必须运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件，软件等环境因素，有时容易掩盖算法本身的优劣。因此，通常采用的评估方法不是事后统计，而是事前分析估算的方法。

(2)事前分析估算法
一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

一句的算法采用何种策略。
问题的规模，例如求 100 以内还是 1000 以内的素数。
书写程序的语言，对于同一个算法，事先语言的级别越高，执行效率就越低。
编译程序所产生的及其代码的质量。
机器执行指令的速度。

显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。

撇开这些与计算机硬件，软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖与问题的规模 (通常用整数量 n 表示)，或者说，它是问题规模的函数。

一个算法是由控制结构 (顺序、分支和循环 3 种) 和原操作(指固有数据类型的操作)构成的，则算法时间取决于两者的综合结果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。

例如，在 NXN 矩阵相乘的算法中，“乘法” 运算是 “矩阵相乘问题” 的基本操作。整个算法的执行时间与该基本操作(乘法)重复执行的次数 n[sup]3[/sup] 成正比，记作 T(n) = O(n[sup]3[/sup]) 。关于矩阵相乘见：http://www.groad.net/bbs/read.php?tid-1168.html
可以将矩阵相乘问题抽象为：

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

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n) ，算法的时间量度记作：

T(N) = O( f(n) )

它表示随着问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的 渐近时间复杂度 (asymptotic time complexity) ，简称时间复杂度。

显然，被称作问题的基本操作的原操作应该是其重复执行次数和算法的执行时间成正比的原操作，在多数情况下，它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。语句的频度 (frequency count) 指的是该语句重复执行的次数，例如，在下列 3 个程序段中：
(a) { ++x; s = 0; }
(b) for (i = 1; i <= n; ++i) {++x; s += x; }
(c) for (j = 1; j <= n; ++j )
          for (k = 1; k <= n; ++k) { ++x; s += x)}

这里，3 个程序段中含有 "x 增 1“ 的语句的频度分别为 1, n 和 n[sup]2[/sup] ，则这 3 个程序段的时间复杂度分别为 O(1) , O(n) O(n[sup]2[/sup]) ，分别称为常量阶、线性阶和平方阶。算法还可能呈现的时间复杂度有对数阶 O(log n) ， 指数阶 O(2[sup]n[/sup]) 等。不同数量级事件安复杂度的性状如下图所示：

由图中可见，我们应该尽可能选用多项式 O(n[sup]2[/sup]) 的算法，而不希望用指数阶的算法。

一般情况下，对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反应不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。

由于算法的时间复杂度考虑的只是对于问题规模 n 的增长率，则在难以精确计算基本操作执行次数(或语句频度)的情况下，只需求出它关于 n 的增长率或阶即可。例如，在下列程序段中：

for (i = 2; i <= n; ++i)
          for (j = 2; j <= i -1; ++j) {++x; a[j] = x;}

语句 ++x 的执行次数关于 n 的增长率为 n[sup]2[/sup] ，它是语句频度表达式 (n-1)(n-2)/2 中增长的项。

从两个 for 循环可以看到，当 i = 3 时，第 2 个 for 循环中的语句才可以得到执行，也就是说从 n - 2 开始第 2 个 for 开始得到执行。那么在第 2 个 for 中就有： i = 3 时，循环体执行 1 次 i = 4 时，循环体执行 2 次 .... 总共的循环次数就是 1 + 2 + 3 + ... + (n - 2) ，这个数列一共有 (n - 2) 项这样数列的和为： ( (1 + (n - 2) ) x (n - 2) ) / 2 ，即为 (n-1)(n-2)/2