数据结构（Java语言描述·微课版）
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

1.3.3 算法效率的评价

一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法的执行时间取决于二者的综合结果。为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本运算的原操作，算法执行的时间大致为基本运算所需的时间与其运行次数（一条语句的运行次数称为语句频度）的乘积。

微课1-3　算法效率的评价

显然，在一个算法中，执行的基本运算次数越少，其执行时间就相对越少；执行基本运算的次数越多，其运行时间也相对越多。换言之，一个算法的执行时间可以看成基本运算执行的次数。

算法基本运算次数T(n)是问题规模n的某个函数f(n)，记作

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

其中，记号“O”读作“大欧”（值数量级），它表示随问题规模n的增大，算法执行时间的增长和f(n)的增长率相同，称为算法的时间复杂度。

“O”的形式定义为：若f(n)是正整数n的一个函数，则T(n)=O(f(n))表示存在一个正的常数M，使得当n≥n0时都满足|T(n)|≤M|f(n)|，也就是只求出T(n)的最高阶，忽略其低阶项和常数，这样既可以简化计算，又可以较为客观地反映当n很大时算法的效率。

一个没有循环的算法中基本运算次数与问题规模n无关，记为O(1)，也称作常数阶。一个只有一重循环的算法中基本次数与问题规模n的增长呈线性增大关系，记为O(n)，也称线性阶。例如，以下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; }

含基本操作“++x”的语句频度分别为1、n和n2，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。各种不同数量级对应的值存在如下关系：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)

例1-4　分析以下算法的时间复杂度。

void fun(int a[],int n,int k)
{
    int i;
    i = 0;                                                      //语句（1）
    while(i < n && a[i] != k)                                   //语句（2）
        i ++;                                                   //语句（3）
    return (i);                                                 //语句（4）
}

解　该算法完成在一维数组a[n]中查找给定值k的功能。语句（3）的频度不仅与问题规模n有关，还与输入实例中a的各个元素取值是否等于k的取值有关，即与输入实例的初始状态有关。若a中没有与k相等的元素，则语句（3）的频度为n；若a中的第一个元素a[0]等于k，则语句（3）的频度是常数0。在这种情况下，可用最坏情况下的时间复杂度作为算法的时间复杂度。这样做的原因是，最坏情况下的时间复杂度是在任何输入实例里运行时间的上界。

有时也可以选择以算法的平均时间复杂度作为讨论目标。所谓平均时间复杂度，是指所有可能的输入实例在以等概率出现的情况下算法的期望运行时间与问题规模n的数量级的关系。例1-4中，k出现在任何位置的概率相同，都为1/n，则语句（3）的平均时间复杂度为

(0+1+2+…+(n−1))/n = (n−1)/2

它决定此程序的平均时间复杂度的数量级为O(n)。

例1-5　分析以下算法的时间复杂度。

float RSum(float list[],int n)
{
    count ++;
    if(n){
        count ++;
        return RSum(list,n-1) + list[n-1];
    }
    count ++;
    return 0;
}

解　例1-5是求数组元素之和的递归程序。为了确定这一递归程序的程序步，首先考虑当n=0时的情况。显然，当n=0时，程序只执行if条件判断语句和第二条return语句，所需程序步数为2。当n>0时，程序在执行if条件判断语句后，将执行第一条return语句。此return语句不是简单返回，而是在调用函数RSum(list,n−1)后，再执行一次加法运算后返回。

设RSum(list,n)的程序步为T(n)，则RSum(list,n−1)为T(n−1)，那么，当n>0时，T(n)=T(n−1)+2。于是有

这是一个递推关系式，它可以通过转换成如下公式来计算

根据上述结果可知，该程序的时间复杂度为线性阶，即O(n)。

上一章目录下一章