分析算法时间复杂度的方法-白红宇

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

阅读量：5249 次

发布时间：2019-06-14

本文共 4053 字，大约阅读时间需要 13 分钟。

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);