算法時(shí)間復(fù)雜度的分析方法研究

周士紅

廣東培正學(xué)院，廣東廣州，510830

0 引言

評(píng)價(jià)一個(gè)算法性能的指標(biāo)有很多，比如易讀性、健壯性、可維護(hù)性、可擴(kuò)展性、效率等等，其中效率是衡量算法性能的核心和靈魂。用來度量算法效率的兩個(gè)指標(biāo)為時(shí)間性能和空間性能，其中時(shí)間性能就是指算法所需要的執(zhí)行時(shí)間。不考慮與計(jì)算機(jī)軟硬件有關(guān)的因素，影響算法時(shí)間性能的最主要因素是問題規(guī)模（即輸入量的多少，用n來表示）[1]。幾乎所有的算法對(duì)于規(guī)模更大的輸入都需要運(yùn)行更長的時(shí)間，所以算法執(zhí)行過程中所需要的時(shí)間T是問題規(guī)模n的函數(shù)，記作T(n)。但是由于受到各種因素的影響，要精確地表示算法的運(yùn)行時(shí)間函數(shù)是非常困難的，所以可以采用時(shí)間復(fù)雜度這一指標(biāo)來度量算法執(zhí)行時(shí)間的增長趨勢。

1 基本語句與時(shí)間復(fù)雜度

算法是由若干條語句構(gòu)成的，若要計(jì)算這個(gè)算法的執(zhí)行時(shí)間，其實(shí)就是求算法中每條語句的執(zhí)行時(shí)間的總和[2]。而執(zhí)行一條語句所用的時(shí)間為執(zhí)行次數(shù)與執(zhí)行一次所需時(shí)間的乘積，而一條語句執(zhí)行一次所需的單位時(shí)間是一定的，所以對(duì)算法的執(zhí)行時(shí)間影響最大的是語句的執(zhí)行次數(shù)，也稱為語句的頻度[3]。在一個(gè)算法的所有語句中，某些語句的執(zhí)行次數(shù)對(duì)整個(gè)算法的執(zhí)行次數(shù)起決定性的影響，這樣的語句稱為基本語句。當(dāng)問題規(guī)模充分大時(shí)，基本語句對(duì)算法執(zhí)行時(shí)間的貢獻(xiàn)最大，所以可以用基本語句的執(zhí)行次數(shù)來衡量算法執(zhí)行時(shí)間的增長趨勢，這種方式簡稱算法的時(shí)間復(fù)雜度，記作T(n)=O(f(n))[4]。

常見的時(shí)間復(fù)雜度有常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)等[5]。按數(shù)量級(jí)由小到大依次排列為：O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(nk)＜O(2n)。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率就會(huì)不斷降低。一般來說，在設(shè)計(jì)算法時(shí)要設(shè)計(jì)具有多項(xiàng)式時(shí)間復(fù)雜度的算法，而具有指數(shù)時(shí)間復(fù)雜度的算法，只有當(dāng)問題規(guī)模足夠小的時(shí)候才可使用[5]。

2 算法中語句的結(jié)構(gòu)

在數(shù)據(jù)結(jié)構(gòu)與算法的前序課程中我們學(xué)過程序流程的三種控制結(jié)構(gòu)分別為順序控制結(jié)構(gòu)、選擇控制結(jié)構(gòu)和循環(huán)控制結(jié)構(gòu)，算法的基本語句就存在于這三種結(jié)構(gòu)中。下面我們分析以下三種結(jié)構(gòu)對(duì)算法時(shí)間復(fù)雜度的影響。

2.1 順序結(jié)構(gòu)的時(shí)間復(fù)雜度

以上算法由三條順序結(jié)構(gòu)的語句組成，每條語句執(zhí)行次數(shù)都為1，即每條語句都可以在單位時(shí)間內(nèi)完成，所以該算法的時(shí)間復(fù)雜度為T(n)=O(1)。不失一般性，因?yàn)轫樞蚪Y(jié)構(gòu)的執(zhí)行過程都是一步一步完成的，所以其時(shí)間復(fù)雜度為常數(shù)階。

2.2 選擇結(jié)構(gòu)的時(shí)間復(fù)雜度

以上算法中有一個(gè)簡單的選擇結(jié)構(gòu)，每條語句的執(zhí)行次數(shù)為1，所以也是可以在單位時(shí)間內(nèi)完成，所以時(shí)間復(fù)雜度為T(n)=O(1)。不失一般性，因?yàn)檫x擇結(jié)構(gòu)的執(zhí)行過程也是一步一步完成的，所以其時(shí)間復(fù)雜度為常數(shù)階。

2.3 循環(huán)結(jié)構(gòu)的時(shí)間復(fù)雜度

在以上算法中語句x++為基本語句，其執(zhí)行次數(shù)受循環(huán)變量i的影響，即從0到n-1一共執(zhí)行n次，所以時(shí)間復(fù)雜度為T(n)=O(n)。

通過以上分析可以看出，順序結(jié)構(gòu)和選擇結(jié)構(gòu)的時(shí)間復(fù)雜度都為常數(shù)階。當(dāng)算法中有循環(huán)結(jié)構(gòu)，并且問題規(guī)模足夠大時(shí)，順序結(jié)構(gòu)和選擇結(jié)構(gòu)對(duì)算法執(zhí)行時(shí)間的影響幾乎可以忽略不計(jì)。所以以下主要針對(duì)循環(huán)結(jié)構(gòu)的時(shí)間復(fù)雜度進(jìn)行計(jì)算方法的分析。

3 算法時(shí)間復(fù)雜度的計(jì)算方法

通常情況下，算法分為非遞歸算法和遞歸算法，以下分情況討論。

3.1 非遞歸算法的時(shí)間復(fù)雜度的分析

通過上面的分析可以得出，當(dāng)問題規(guī)模足夠大時(shí)，對(duì)算法時(shí)間復(fù)雜度起決定性作用的是循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)是由兩部分構(gòu)成的，包括循環(huán)條件和循環(huán)體。根據(jù)循環(huán)條件與循環(huán)體之間是否有關(guān)系可以將循環(huán)結(jié)構(gòu)分為：①循環(huán)條件和循環(huán)體之間相互獨(dú)立；②循環(huán)條件之間有關(guān)系，但與循環(huán)體獨(dú)立；③循環(huán)條件與循環(huán)體之間有關(guān)系。不同類型的循環(huán)結(jié)構(gòu)，其時(shí)間復(fù)雜度有不同的分析方法。

3.1.1 直接分析法

當(dāng)循環(huán)結(jié)構(gòu)中循環(huán)條件與循環(huán)體相互獨(dú)立，并且循環(huán)條件的執(zhí)行次數(shù)比較容易計(jì)算時(shí)，可以直接分析算法的時(shí)間復(fù)雜度。例如有以下算法。

例1是給定 n個(gè)元素的數(shù)組a[n]，求其中奇數(shù)有多少個(gè)。由代碼段可以看出，該函數(shù)中只有一層for循環(huán)，而該循環(huán)執(zhí)行了n次，因此時(shí)間復(fù)雜度為T(n)=O(n)。

例2算法中的循環(huán)結(jié)構(gòu)是雙重嵌套循環(huán)，并且循環(huán)條件和循環(huán)體之間都是相互獨(dú)立的?？梢灾庇^地看出，每當(dāng)外層循環(huán)的i取一個(gè)值時(shí)，內(nèi)層循環(huán)都執(zhí)行n次，所以該算法的時(shí)間復(fù)雜度為T(n)=O(n m)。

3.1.2 求乘積法

在嵌套循環(huán)中，當(dāng)循環(huán)條件之間有關(guān)系，但與循環(huán)體獨(dú)立時(shí)，可以用乘積法計(jì)算時(shí)間復(fù)雜度。在例3算法中，內(nèi)層循環(huán)條件j的執(zhí)行次數(shù)受外層循環(huán)條件i的執(zhí)行次數(shù)的影響，所以我們無法非常直接地分析算法的時(shí)間復(fù)雜度。

分析以上算法，其中m=m+1為基本語句，與循環(huán)變量i和j沒有關(guān)系，所以假定用1來代表該基本語句，其執(zhí)行次數(shù)為：。當(dāng)問題規(guī)模足夠大時(shí)，可以忽略n的影響，所以其時(shí)間復(fù)雜度為T(n)=O(n2)。

3.1.3 轉(zhuǎn)換法

在某些算法中，因?yàn)檠h(huán)條件與循環(huán)體中的某些語句有關(guān)系，可能導(dǎo)致無法非常直觀地計(jì)算語句的執(zhí)行次數(shù)。但是有些循環(huán)結(jié)構(gòu)之間可以進(jìn)行相互轉(zhuǎn)換，轉(zhuǎn)換后可以更方便計(jì)算。例如有以下算法。

對(duì)于以上算法，因?yàn)檠h(huán)條件和循環(huán)體中都有i，所以無法直觀地計(jì)算語句的執(zhí)行次數(shù)。但是while循環(huán)和for循環(huán)在某些情況下是可以相互轉(zhuǎn)化的，所以例4可以轉(zhuǎn)換為如下算法：

在轉(zhuǎn)換后的算法中，x++為基本語句。假設(shè)基本語句的執(zhí)行次數(shù)為T(n)，則執(zhí)行完后有i=2T(n)。而i<=n，所以2T(n)≤n，即T(n)≤log2n，所以算法的時(shí)間復(fù)雜度為T(n)=O(log2n)。

3.1.4 數(shù)學(xué)歸納法

在某些更為復(fù)雜的算法中，當(dāng)循環(huán)次數(shù)與循環(huán)體中的某些語句執(zhí)行有聯(lián)系，并且循環(huán)結(jié)構(gòu)無法進(jìn)行轉(zhuǎn)換或者轉(zhuǎn)換后也無法使計(jì)算變得簡單，此時(shí)可以用數(shù)學(xué)歸納法分析循環(huán)變量與語句執(zhí)行次數(shù)的關(guān)系，進(jìn)而得出算法的時(shí)間復(fù)雜度。例如有以下算法。

但是轉(zhuǎn)換后也無法直接計(jì)算時(shí)間復(fù)雜度，所以可以采用數(shù)學(xué)歸納法尋找循環(huán)次數(shù)與sum之間的關(guān)系。對(duì)于例5假定循環(huán)次數(shù)為m，則有：

當(dāng)m=1時(shí)，i=1，sum=0+1；

當(dāng)m=2時(shí)，i=2，sum=0+1+2；

當(dāng)m=3時(shí)，i=3，sum=0+1+2+3；

……

當(dāng)執(zhí)行m次時(shí)，i=m，sum=0+1+2+3+……+m=。

整理后得m(m+1)=2(n-1)，即m2+m=2n-2。

m2為負(fù)值，不符合要求，舍棄，只取m1。所以可以看出該算法的時(shí)間復(fù)雜度為T(n)=O()。

3.1.5 求和法

當(dāng)算法中存在多個(gè)并列的循環(huán)結(jié)構(gòu)時(shí)，可以用求和法來計(jì)算時(shí)間復(fù)雜度。例如有以下算法。

在以上算法中，并列存在兩個(gè)循環(huán)結(jié)構(gòu)。第一個(gè)循環(huán)結(jié)構(gòu)為雙重循環(huán)，其時(shí)間復(fù)雜度用直接分析法可以得出為O(n2)。第二個(gè)循環(huán)結(jié)構(gòu)為單層循環(huán)，其時(shí)間復(fù)雜度也可以直接得出為O(n)。所以整個(gè)算法的時(shí)間復(fù)雜度為T(n)=O(n)+O(n2)。當(dāng)問題規(guī)模足夠大時(shí)，可以忽略O(shè)(n)對(duì)O(n2)的影響，因此整段代碼的時(shí)間復(fù)雜度為T(n)=O(n2)。

3.2 遞歸算法的時(shí)間復(fù)雜度的分析

遞歸算法簡單來說就是一個(gè)函數(shù)直接或間接調(diào)用自身的一種方法。通過遞歸，可以將一個(gè)原本非常大型的問題轉(zhuǎn)換為一個(gè)與原有問題相似但是規(guī)模比較小的問題來求解。對(duì)于遞歸算法通常采用遞推法來求解其時(shí)間復(fù)雜度，例如有以下算法。

假設(shè)該函數(shù)的運(yùn)行時(shí)間為T(n)。函數(shù)中s=1的運(yùn)行時(shí)間為O(1)，s=n*fun(n-1)的運(yùn)行時(shí)間為T(n-1)+O(1)，即：

由此可得：

所以該遞歸函數(shù)的時(shí)間復(fù)雜度為T(n)=O(n)。

4 總結(jié)

對(duì)于算法效率的分析有事前分析和事后統(tǒng)計(jì)兩種方法。事后統(tǒng)計(jì)指的是通過編寫程序?qū)崿F(xiàn)算法后進(jìn)行定量分析，這種方式需要花費(fèi)較多的時(shí)間和精力，并且容易受到計(jì)算機(jī)軟硬件等環(huán)境因素的影響。所以通常采用事前分析的方法來估算，而時(shí)間復(fù)雜度就是一個(gè)通過增長趨勢來度量算法執(zhí)行時(shí)間的指標(biāo)。算法時(shí)間復(fù)雜度的分析貫穿在數(shù)據(jù)結(jié)構(gòu)教材中各種算法的性能分析中，學(xué)會(huì)分析算法的時(shí)間復(fù)雜度可以幫助我們?cè)O(shè)計(jì)出更高效、更優(yōu)化的算法。但是在教學(xué)過程中，由于時(shí)間復(fù)雜度概念比較抽象，并且對(duì)于某些算法來說其計(jì)算過程比較復(fù)雜，所以時(shí)間復(fù)雜度一直是教學(xué)過程中的難點(diǎn)。論文對(duì)算法時(shí)間復(fù)雜度的相關(guān)知識(shí)和理論進(jìn)行了簡單介紹，通過分析得出了在算法中對(duì)其時(shí)間復(fù)雜度影響最大的是循環(huán)結(jié)構(gòu)，然后根據(jù)循環(huán)結(jié)構(gòu)不同的類型給出了對(duì)于時(shí)間復(fù)雜度不同的求解方法，使學(xué)生對(duì)算法時(shí)間復(fù)雜度的理解和掌握更為系統(tǒng)。