1.3.4　算法渐进复杂性

视频讲解

随着经济的发展、社会的进步、科学研究的深入，人们要求用计算机解决的问题越来越复杂，规模也越来越大。对解决这类问题的算法进行分析时，如果精打细算，即把所有的相关因素及元运算都考虑进去，那么由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。

为此，对于规模充分大、结构又十分复杂的这类问题的解决算法，人们提出了其复杂性分析应如何简化的问题。

视频讲解

视频讲解

视频讲解

1．算法渐进复杂性的引入

假设算法A的运行时间表达式T₁（n）为

T₁（n）=30n4+20n3+40n2+46n+100　（1-1）

算法B的运行时间表达式T₂（n）为

T₂（n）=1000n3+50n2+78n+10　（1-2）

显然，当问题的规模足够大的时候，例如n=100万，算法的运行时间将主要取决于时间表达式的第一项，其他项的执行时间只有第一项的几十万分之一，可以忽略不计。随着n的增大，第一项的常数对算法的执行时间也变得不重要了。

于是，算法A的运行时间可以记为：（n）≈n4，称n4为（n）的阶。

同理，算法B的运行时间可以记为：（n）≈n3，称n3为（n）的阶。

由上述分析可以得出一个结论：随着问题规模的增大，算法时间复杂性主要取决于运行时间表达式的阶。如果要比较两个算法的效率，只需比较它们的阶就可以了。

定义1　设算法的运行时间为T（n），如果存在T∗（n），使得

就称T∗（n）为算法渐进时间复杂性。

可见，问题规模充分大时，T（n）和T∗（n）近似相等。因此，在算法分析中，对算法时间复杂性和算法渐进时间复杂性往往不加区分，并常用后者来对一个算法时间复杂性进行衡量，从而简化了大规模问题的时间复杂性分析。

2．渐进意义下的记号

与简化的复杂性相匹配，引入了渐近意义下的记号O、o、Ω、w、Θ，下面讨论O、Ω、Θ三个记号。设T（n）、f（n）和g（n）是正数集上的正函数，其中n是问题规模。

（1）渐近上界记号：O（big-oh）。

定义2　若存在两个正常数c和n₀，使得当n≥n₀时，都有T（n）≤cf（n），则称T（n）=O（f（n）），即f（n）是T（n）的上界。换句话说，在n满足一定条件的范围内，函数T（n）的阶不高于函数f（n）的阶。

【例1-1】　用O表示T（n）=10n+4的阶。

存在c=11，n₀=4，使得当n≥n₀都有

T（n）=10n+4≤10n+n=11n

令f（n）=n，可得

T（n）≤cf（n）

即T（n）=O（f（n））=O（n）。

应该指出，根据符号O的定义，用它评估算法的复杂性得到的只是问题规模充分大时的一个上界。这个上界的阶越低，则评估就越精确，结果就越有价值。如果有一个新的算法，其运行时间的上界低于以往解同一问题的所有其他算法的上界，就认为建立了一个解该问题所需时间的新上界。

常见的几类时间复杂性有：

O（1）：常数阶时间复杂性。它的基本运算执行的次数是固定的，总的时间由一个常数来限界，此类时间复杂性的算法运行时间效率最高。

O（n）、O（n2）、O（n3）、……：多项式阶时间复杂性。大部分算法的时间复杂性是多项式阶的，通常称这类算法为多项式时间算法。O（n）称为1阶时间复杂性，O（n2）称为2阶时间复杂性，O（n3）称为3阶时间复杂性……。

O（2n）、O（n!）和O（nn）：指数阶时间复杂性。这类算法的运行效率最低，这种复杂性的算法根本不实用。如果一个算法的时间复杂性是指数阶的，通常称这个算法为指数时间算法。

O（nlogn）和O（logn）：对数阶时间复杂性。

以上几种复杂性的关系为

O（1）<O（logn）<O（n）<O（nlogn）<O（n2）<O（n3）<O（2n）<O（n!）<O（nn）其中，指数阶时间复杂性最常见的是O（2n），当n取值很大时，指数时间算法和多项式时间算法所需运行时间的差距将非常悬殊。因为，对于任意的m≥0，总可以找到n₀（n₀>0），当n≥n₀时，有2n≥nm。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，就取得了一个伟大的成就。

另外，按照O的定义，容易证明如下运算规则成立，这些规则对后面的算法分析是非常有用的。

①O（f）+O（g）=O（max（f，g））。

②O（f）+O（g）=O（f+g）。

③O（f）O（g）=O（fg）。

④如果g（n）=O（f（n）），则O（f）+O（g）=O（f）。

⑤O（Cf（n））=O（f（n）），其中C是一个正的常数。

⑥f=O（f）。

规则①的证明：

设F（n）=O（f）。按照符号O的定义，存在正常数c₁和n₁，使得当n≥n₁时，都有F（n）≤c₁f。

类似地，设G（n）=O（g）。按照符号O的定义，存在正常数c₂和n₂，使得当n≥n₂时，都有G（n）≤c₂g。

令c₃=max{c₁，c₂}，n₃=max{n₁，n₂}，h（n）=max{f，g}，则使得当n≥n₃时，有

F（n）≤c₁f≤c₁h（n）≤c₃h（n）

类似地，有

G（n）≤c₂g≤c₂h（n）≤c₃h（n）

因此

O（f）+O（g）=F（n）+G（n）

≤c₃h（n）+c₃h（n）

=2c₃h（n）

即，存在c=2c₃，n₃，使得n≥n₃时，有O（f）+O（g）≤ch（n）恒成立，因此

O（f）+O（g）=O（h（n））

=O（max（f，g））

其余规则的证明与此类似，感兴趣的读者可自行进行证明。

（2）渐近下界记号：Ω（big-omega）。

定义3　若存在两个正常数c和n₀，使得当n≥n₀时，都有T（n）≥cf（n），则称T（n）=Ω（f（n）），即f（n）是T（n）的下界。换句话说，在n满足一定条件的范围内，函数T（n）的阶不低于函数f（n）的阶。它的概念与O的概念是相对的。

【例1-2】　用Ω表示T（n）=30n4+20n3+40n2+46n+100的阶。

存在c=30，n₀=1，使得当n≥n₀都有

T（n）≥30n4

令f（n）=n4，可得

T（n）≥cf（n）

即T（n）=Ω（f（n））=Ω（n4）。

同样，用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。如果有一个新的算法，其运行时间的下界低于以往解同一问题的所有其他算法的下界，就认为建立了一个解该问题所需时间的新下界。

（3）渐近精确界记号：Θ（big-theta）。

定义4　若存在3个正常数c₁、c₂和n₀，使得当n≥n₀时，都有c₂f（n）≤T（n）≤c₁f（n），则称T（n）=Θf（n）。Θ意味着在n满足一定条件的范围内，函数T（n）和f（n）的阶相同。由此可见，Θ用来表示算法的精确阶。

【例1-3】　用Θ表示T（n）=20n2+8n+10的阶。

①存在c₁=29，n₀=10，使得当n≥n₀时都有

T（n）≤20n2+8n+n=20n2+9n≤20n2+9n2=29n2

令f（n）=n2，可得

T（n）≤c₁f（n）

即T（n）=O（f（n））=O（n2）。

②存在c₂=20，n₀=10，使得当n≥n₀时都有

T（n）≥20n2

令f（n）=n2，可得

T（n）≥c₂f（n）

即T（n）=Ω（f（n））=Ω（n2）。

③由此可见，存在c₁=29、c₂=20和n₀=10，使得当n≥n₀时都有

c₂f（n）≤T（n）≤c₁f（n）

令f（n）=n2，可得T（n）=Θf（n）=Θ（n2）。

定理1　若T（n）=a_mnm+a_m-1nm-1+…+a₁n+a₀（a_i>0，0≤i≤m）是关于n的一个m次多项式，则T（n）=O（nm），且T（n）=Ω（nm），因此有T（n）=Θ（nm）。

证明：

①根据O的定义，取n₀=1，当n≥n₀时都有

令

则有T（n）≤c₁nm，由此可得T（n）=O（nm）。

②根据Ω的定义，取n₀=1，当n≥n₀时都有

T（n）≥a_mnm

令

c₂=a_m

则有T（n）≥c₂nm，由此可得T（n）=Ω（nm）。

③根据Θ的定义，取c₁、c₂和n₀，当n≥n₀时都有

c₂nm≤T（n）≤c₁nm

至此可证明T（n）=Θ（nm）。

3．算法的运行时间T（n）建立的依据

如1.3.2节所述可知，要想精确地表示出算法的运行时间是很困难的。考虑到算法分析的主要目的是比较求解同一个问题的不同算法的效率。因此，在算法分析中只是对算法的运行时间进行粗略估计，得出其增长趋势即可，而不必精确计算出具体的运行时间。

（1）非递归算法中T（n）建立的依据。

为了求出算法的时间复杂性，通常需要遵循以下步骤：

①选择某种能够用来衡量算法运行时间的依据。

②依照该依据求出运行时间T（n）的表达式。

③采用渐进符号表示T（n）。

④获得算法的渐进时间复杂性，进行进一步的比较和分析。

其中，步骤①是最关键的，它是其他步骤能够进行的前提。通常衡量算法运行时间的依据是基本语句，所谓基本语句是指对算法的运行时间贡献最大的原操作语句。

当算法的时间复杂性只依赖问题规模时，基本语句选择的标准是：必须能够明显地反映出该语句操作随着问题规模的增大而变化的情况，其重复执行的次数与算法的运行时间成正比，多数情况下是算法最深层循环内的语句中的原操作；对算法的运行时间贡献最大，在解决问题时占支配地位。这时，就可以采用该基本语句的执行次数来作为运行时间T（n）建立的依据，即用其执行次数对运行时间T（n）进行度量。

【例1-4】　求出一个整型数组中元素的最大值。

算法描述如下：

     int array Max(int a[],int n)
     {
       int max=a[0];
       for(int i=1;i<n;i++)
          if(a[i]>max)
                max=a[i];
       return max;
     }

在该算法中，问题规模就是数组a中的元素个数。显然，执行次数随问题规模的增大而变化，且对算法的运行时间贡献最大的语句是if（a[i]>max），因此将该语句作为基本语句。显然，每执行一次循环，该语句就执行一次，循环变量i从1变化到n-1，因而该语句共执行了n-1次，由此可得T（n）=n-1=O（n）。

当算法的时间复杂性既依赖问题规模又依赖输入序列时，例如插入、排序、查找等算法，如果要合理全面地对这类算法的复杂性进行分析，则要从最好、最坏和平均情况三方面进行讨论。

【例1-5】　在一个整型数组中顺序查找与给定整数值K相等的元素（假设数组中至多有一个元素的值为K）。

算法描述如下：

     int find(int a[],int n,int K)
     {
          int i;
         for(i=0;i<n;i++)
             if(a[i]==K)
                  break;
         return i;
     }

在该算法中，问题的规模由数组中的元素个数决定。显然，对算法的运行时间贡献最大的语句是if（a[i]==K），因此将该语句作为基本语句。但是该语句的执行次数不但依赖问题的规模，还依赖于输入数据的初始状态。

如果a[0]的元素为K，该语句的执行次数为1，这是最好情况，即T_min（n）=O（1）。如果数组a[n-1]的元素为K，则该语句的执行次数为n，这是最坏情况，即T_max（n）=O（n）。如果数组a中的元素呈等概率分布，则该语句的执行次数为，这是平均情况，即T_avg（n）=。

这3种情况下的时间复杂性分别从不同角度反映了算法的时间效率，各有各的用处，各有各的局限性。一般来说，最好情况不能用来衡量算法的时间复杂性，因为它发生的概率太小了。实践表明可操作性最好且最有实际价值的是最坏情况下的时间复杂性，它至少使人们知道算法的运行时间最坏能坏到什么程度。如果输入数据呈等概率分布，要以平均情况来作为运行时间的衡量。

（2）递归算法中T（n）建立的依据。

对于递归算法的时间复杂性分析方法将在1.4.4节讲述。

4．算法所占用的空间S（n）建立的依据

在渐进意义下所定义的复杂性的阶、上界与下界等概念，也同样适用于算法空间复杂性的分析。如1.3.3节所述，本书讨论算法的空间复杂性只考虑算法在运行过程中所需要的辅助空间。

【例1-6】　用插入法升序排列数组s中的n个元素。

算法描述如下：

     void insert_sort(int n,int s[])
      { int a,i,j;
            for(i=1;i<n;i++)
              {
                  a=s[i];
                  j=i-1;
                  while(j>=0&&s[j]>a)
                    {
                         s[j+1]=s[j];
                         j--;
                    }
                  s[j+1]=a;
           }
       }

在算法insert_sort中，为参数表中的形参变量n和s所分配的存储空间，是属于为输入输出数据分配的空间。那么，该算法所需的辅助空间只包含为a、i和j分配的空间，显然insert_sort算法的空间复杂性是常数阶，即S（n）=O（1）。

另外，若一个算法为递归算法，其空间复杂性是为实现递归所分配的堆栈空间的大小，具体分析方法将在1.4.4节讲述。