分析算法时间复杂度的方法

1.1 频度统计法。

频度统计法指以程序中语句执行次数的多少作为算法时间度量分析的一种方法。通常情况下，算法的时间效率主要取决于程序中包含的语句条数和采用的控制结构这两者的综合效果。因此，最原始且最牢靠的方法是求出所有主要语句的频度f(n)，然后求所有频度之和。

例如：如下形式的语句段：

for (i=1;i<n;i++)

{ y++;

for (j=0;j<(2*n);j++)

x++;

}

这个由两个for语句构成的程序段，外循环的重复执行次数是n－1次，内循环的单趟重复执行次数是2×n次。因此，语句y++的频度为n－1，语句x++的频度为2×n×（n－1）。

所以， T（n）＝O（∑f（n））＝O（n－1+2×n2－2×n）

取增长最快的一项作为数量级，则 T（n）＝O（n2）

该方法简单，结果绝对精确，适用于大多数程序。但分析算法时间效率时往往只需计算出其大致数量级，此时，采用频度估算法即可。

1.2 频度估算法。

先找出对于所求解的问题来说是共同的原操作，并求出原操作的语句频度f(n)，然后直接以f(n)衡量T(n)。在使用频度估算法时应注意到一个显著的标志，就是原操作往往是最内层循环的循环体，并且，完成该操作所需的时间与操作数的具体取值无关。这种方法比较适合于带有多重循环的程序。

例如：数学中求两个矩阵乘法的常规方法是用了一个三重循环，如下：

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]=c[i][j]+a[i][k]*b[k][j];

}

}

这个程序段的原操作是处于最内层循环的语句c[i][j]=c[i][j]+a[i][k]*b[k][j]，该语句的重复执行次数即原操作的频度是n3，可以直接得出：该算法的时间复杂度T（n）＝O（n3）。

对于一些复杂的算法，可以将算法分解成容易估算的几个部分，利用频度估算法分别求出这几部分的时间复杂度，然后利用求和的原则得到整个算法的时间复杂度。

频度估算法的优点是结果较精确，方法简单且易掌握，但对于原操作的频度不易直接确定的程序，却无能为力。

1.3 频度未知数法。

当不能直接求出原操作的重复执行次数f(n)，但通过对程序主要语句的分析，确信可以通过间接的方式计算得出。其基本规律是：首先将原操作的频度设为一个未知数，然后根据原操作执行结束的条件及特征列方程求出它，如果结果是不等式，取其极大值。

比如程序段： i=s=0;

while (s<n)

{ i++; s+=i; }

分析：该程序段的原操作是语句s+=i，无法一眼看出原操作的频度f（n）。为求得f（n），设循环体共执行了k次后结束，即令f（n）＝k，则根据语义，可以得出

1＋2＋3＋……＋k>=n 且 1＋2＋3＋……＋（k－1）<n

由以上两式，可得方程组

取其极值，并忽略常数对数量级的影响，可得 T（n）＝O（ ）=O（ ）

1.4 列举频度归纳法。

程序中经常会出现带有倍增型循环的情况。倍增循环指内循环的执行次数随外循环控制变量而变化的多重循环结构。

例如： m=1;

for (i=1;i<=n;i++)

{ m=m*2;

for (j=1;j<=m;j++)

x++;

}

分析：当外循环变量i分别从1，2，……，一直取到n时，内循环的执行次数依次是2，4，8，……，2n，这是一个几何级数序列，其中每一项的值是前一项的常数倍。

因此，

这种算法的特征是，原操作的频度和一个变化的量有关，比如内循环的执行次数依赖于外循环的循环控制变量，或每执行一次循环，循环控制变量将被乘以（除以）一个常数。

再如： for (i=0;i<n;i++)

for (j=i;j<n;j++)

for (k=j;k<n;k++)

x++;

分析：由于最内层for循环控制语句执行1次，其循环体即原操作x++恰好执行了n-j次，因此，整个算法完成时共执行了 次x++语句，而

结论：当分析带有倍增循环结构程序的运行时间开销时，需要把每次执行循环的时间累加起来，其结果表达式往往就被转化为一个级数求和的问题。

1.5 频度期望值法。

当原操作的执行次数不仅依赖于问题的规模，而且随原始数据集状态的不同而不同时，往往需要根据原始数据的分布特点，考虑数据在某种概率分布下频度的一个平均值。此时，即使问题规模相同，对于不同的特定输入，其时间开销也不同。

在这种情形下，考虑求符合某种概率分布情况下的原操作的平均频度，然后以平均频度的一个数量级作为算法的时间度量。

例如：顺序查找算法

int Search_Seq(Table S，KeyType key)

// Table是查找表类型，KeyType表示关键字类型

{ S.elem[0].key=key；

for (i=S.length；S.elem[i]!=key；i--)；

return i；

}

分析：该算法中的原操作是“将记录的关键字和给定值进行比较”，但根据 for循环的判断条件，比较的次数取决于待查记录在查找表中的位置i。根据所查找数据在查找表中位置的不同，其时间开销可能在一个很大的范围内浮动。为求出时间复杂度，通常转而求“其关键字和给定值进行过比较的记录的个数的平均值”，即“比较次数”的平均频度。一般来说，在进行研究时，为方便讨论，对于经典的查找和排序算法，总是考虑“等概率”条件。

所以，各记录的查找概率依次为：

第i个记录的比较次数 是： ＝n-i+1

故，平均频度

所以，T（n）＝ ＝O（n）

根据原始数据集的分布特点，有些查找问题的检索概率不一定相等，但求解的方法相同，都是求某种概率分布下的一个期望值。对于原操作的执行次数依赖于原始数据排列情况的问题来说，内循环体的执行次数取决于外循环控制变量的情形非常常见，其求解方法也完全适用。例如：大多数静态的排序算法。

需要说明的一点是：数据分布的特点对于很多查找算法效率都会有很大的影响，而平均情况分析并不总是可行。因为，首先要求了解清楚数据是如何分布的。对于这一类问题，有时候要根据各种可能出现的最坏情况来估算算法的时间复杂度。

1.6 递归算法时间复杂度的计算技巧。

递归过程的运行时间一般都能通过一个递归关系式得到很好的体现。根据对递归关系式的不同计算方法，将递归算法的求解方法提炼为如下两种。

1.6.1扩展递归迭代法。

当需要找到一个递归问题的精确答案时，可采用一种递归扩展技术。其基本方法是：方程右边较小的项根据定义被依次替代，如此反复扩展，直到得到一个没有递归式的完整数列，从而将复杂的递归问题转化为了新的求和问题。

例如： float fact(long int n)

{ if (n<0) return(-1);

else if (n==0 || n==1) return(1);

else return(n*fact(n-1));

}

分析：递归函数fact每递归调用自身一次，问题规模就减少1。该函数中出口语句的运行时间为O（1）；调用返回的结果与输入参数相乘，这个操作的运行时间是一个常量可以记为O（1）。因此，函数fact的时间代价就等于该常数加上执行递归调用的时间，可以表示成

C n<=1

T(n)= C为递归调用语句的运行时间，这里是常数O（1）

则，

＝……

所以，函数fact的时间复杂度是O（n）。

利用递归本身的特点采用这种扩展技术求解递归程序的时间效率，是一种保守且可靠的方法。但有些问题，其求和序列的推导可能会是一项比较繁琐而枯燥的纯数学工作。遇到这种情况时，完全可以让个人的经验充分发挥作用，利用经验去猜测答案。

1.6.2上下限猜测法。

先试着猜测答案，找出一个认为是正确的上下限估计，然后再去证明它。如果归纳证明成功，那么再试着收缩上下限；如果证明失败，那么就放松限制重试；一旦上下限符合要求，就得到了所求的答案。

例如：以下方程描述归并排序的运行时间，其数学的推导方法非常繁琐，现用上下限猜测技术来估算其渐进时间复杂度。

1 n=2

T(n)=

不失一般性，先猜测这个递归有一个上限 O（n2），更准确地说，假定T（n）≤n2，通过归纳来证明这个假定是否正确。如果正确，继续收缩上限，猜测一个更小的估计。

为了使计算简便，假定n是2的乘方。初始情况：T(2)=1≤22，显然成立。

假设当i≤n时 T（i）≤i2 成立，要证明对于所有的n=2N，N≥1，T(n) ≤n2能够得到T(2n) ≤(2n)2。

而 T（2n）＝2T（n）＋2n≤2n2＋2n≤4n2≤（2n）2 至此命题得证。

所以，猜测T（n）≤O（n2）是正确的。

但是O（n2）可能是一个很高的估计。如果猜测更小一些，例如T（n）≤cn（c为某个常数），很明显，因为c2n＝2cn，没有为额外的代价n留下余地，使待排序的两块归并在一起，因此T（n）≤cn不可能成立。这样就可以初步得知，真正的代价一定在cn与n2之间。

继续尝试T（n）≤nlog2n。初始情况： T（2）＝1≤（2&#8226;log22）＝2。归纳假设T（n）≤nlog2n，那么：T(2n)=2T(n)+2n≤2nlog2n+2n≤2n(log2n+1) ≤2nlog22n

类似地，还可以证明T（n）≥（nlog2n）。所以，T（n）就是O(nlog2n)。

在求解渐近时间复杂度时，这种猜测技术是一种很有用的技术，当寻找精确解时，就不适用了。

2. 结束语

提倡在解决问题时，首先要详细分析算法的特性及特征，然后再按照不同的特性采用合适的方法区别对待，具体问题具体分析，从而避免不必要的代价和周折，达到快速而准确求解的目的。