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節講述。