趙美勇，崔旭冉，宋思睿，湯繼澳，王夢(mèng)媛

（1.山東科技大學(xué)，濟(jì)南 250000；2.上海政法學(xué)院，上海 201701）

1 時(shí)間復(fù)雜的概念

衡量算法占用CPU時(shí)間的多少稱為時(shí)間性能分析，為了便于從算法本質(zhì)的角度研究算法的時(shí)間性能，常通過(guò)事前估算的方法，研究算法本身的效率，即研究算法本身的運(yùn)算量。算法的運(yùn)算量的大小依賴于問(wèn)題的規(guī)模，則算法的運(yùn)行時(shí)間是問(wèn)題規(guī)模的函數(shù)，故常使用函數(shù)記錄算法的相對(duì)運(yùn)行時(shí)間，稱為時(shí)間復(fù)雜度。時(shí)間復(fù)雜度是一個(gè)函數(shù)，它表示了一個(gè)算法的效率。時(shí)間復(fù)雜度通常用O表示，形如O（n），其中問(wèn)題規(guī)模n是影響程序運(yùn)行時(shí)間的最主要參數(shù)，和程序所需處理的數(shù)據(jù)量有一定的關(guān)系。這樣的函數(shù)和處理的數(shù)據(jù)量有關(guān)系，而不反映具體運(yùn)行時(shí)間（即函數(shù)不反映算法運(yùn)行的絕對(duì)時(shí)間），因?yàn)榫唧w的因素很多，所以時(shí)間復(fù)雜度又被稱為漸進(jìn)時(shí)間復(fù)雜度。數(shù)據(jù)量是影響算法的一個(gè)主要因素，數(shù)據(jù)量越大時(shí)間也就越長(zhǎng)，而時(shí)間復(fù)雜度作為一個(gè)函數(shù)，被抽象成一個(gè)非常簡(jiǎn)單的形式，其目的就是表示時(shí)間效率。不同時(shí)間復(fù)雜度的算法，其時(shí)間和效率的差距是非常大的。

2 常見(jiàn)的幾種時(shí)間復(fù)雜度

時(shí)間復(fù)雜度的類型往往和程序的循環(huán)有關(guān)，具體分析如下：

2.1 線性時(shí)間復(fù)雜度

假設(shè)現(xiàn)有下列待執(zhí)行任務(wù)：給定一組數(shù)據(jù)，并要求找出該數(shù)組中數(shù)值為1的元素個(gè)數(shù)。假設(shè)該數(shù)組的長(zhǎng)度為n，那么很容易得到這樣一個(gè)算法，通過(guò)枚舉每一個(gè)元素的具體數(shù)值與數(shù)值1進(jìn)行比較，此枚舉算法將執(zhí)行n次比較操作。對(duì)于不同的計(jì)算機(jī)，這n次操作所需的時(shí)間具有一定差異，但是執(zhí)行的總次數(shù)n是確定的。如果此時(shí)將這個(gè)數(shù)組長(zhǎng)度變?yōu)?*n，即長(zhǎng)度變?yōu)樵瓉?lái)的兩倍，那么對(duì)應(yīng)的時(shí)間也會(huì)增加一倍。諸如此類的算法，其時(shí)間復(fù)雜度就被稱為線性時(shí)間復(fù)雜度。

2.2 平方時(shí)間復(fù)雜度

將2.1當(dāng)中描述的引例做如下修改：現(xiàn)在有兩個(gè)長(zhǎng)度為n的數(shù)組，此時(shí)需要找到這兩個(gè)數(shù)組里有多少個(gè)元素?cái)?shù)值相等。這時(shí)可以采用以下計(jì)算法，首先枚舉第一個(gè)數(shù)組，每次取出一個(gè)元素，然后繼續(xù)枚舉第二個(gè)數(shù)組，將第一個(gè)數(shù)組和第二個(gè)數(shù)組中的每一個(gè)元素進(jìn)行比較，對(duì)比其數(shù)值是否相同。此時(shí)最多需要比較n*n次，如果將兩個(gè)數(shù)組都擴(kuò)大一倍，那么比較次數(shù)就變成了4*n*n次，即原來(lái)的4倍。諸如此類的算法，其時(shí)間復(fù)雜度就被稱為平方時(shí)間復(fù)雜度。

2.3 對(duì)數(shù)時(shí)間復(fù)雜度

假設(shè)現(xiàn)有一個(gè)已經(jīng)排序的長(zhǎng)度為n的數(shù)組，現(xiàn)在需要找到數(shù)組中是否存在一個(gè)元素且其值為x。在這里不再使用效率較低的枚舉法進(jìn)行逐項(xiàng)對(duì)比。因?yàn)閿?shù)組是已經(jīng)過(guò)排序的，所以每次只需取出當(dāng)前處于區(qū)間最中間位置的元素與數(shù)值x進(jìn)行比較，如果該元素的數(shù)值比x大，則向比這個(gè)數(shù)值更小的方向即左邊繼續(xù)比較，如果數(shù)值偏大，以此類推，進(jìn)行類似的操作逐步比較。這樣最多需要比較log（n）次，此時(shí)將數(shù)組擴(kuò)大兩倍，則需要比較log（2*n）次。諸如此類的算法，其時(shí)間復(fù)雜度就被稱為對(duì)數(shù)時(shí)間復(fù)雜度。

3 優(yōu)化時(shí)間復(fù)雜度

時(shí)間復(fù)雜度的優(yōu)化來(lái)源于很多方面，常在編程時(shí)利用高級(jí)的數(shù)據(jù)結(jié)構(gòu)、優(yōu)化核心算法、犧牲空間復(fù)雜度等方式來(lái)優(yōu)化時(shí)間復(fù)雜度，還可利用一些編程過(guò)程中的特殊指令等。優(yōu)化的具體方法如下：

3.1 利用高級(jí)的數(shù)據(jù)結(jié)構(gòu)

利用高級(jí)的數(shù)據(jù)結(jié)構(gòu)主要針對(duì)一些需用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)的情況，在這種情況下編程人員容易選擇一些設(shè)計(jì)簡(jiǎn)單但是程序本身運(yùn)行起來(lái)較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。此時(shí)，根據(jù)需求選用一種良好的數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化時(shí)間及效率就顯得尤為重要，下面通過(guò)一個(gè)實(shí)例進(jìn)行說(shuō)明：假設(shè)有這樣的一個(gè)需求，給定一個(gè)元素，要求把該元素放到一個(gè)序列的指定位置。此時(shí)我們很容易想到建立一個(gè)數(shù)組，每次插入一個(gè)新數(shù)據(jù)時(shí)，將插入的位置后面的元素全部向后平移一個(gè)單位以騰出一個(gè)位置存放新數(shù)據(jù)。分析這些操作的時(shí)間復(fù)雜度可知，設(shè)需要操作n次，由于數(shù)組剛開(kāi)始是空的，那么最壞的情況是每次都將新數(shù)據(jù)插在數(shù)組的開(kāi)頭，則總共需要操作n*（1+n）/2次，由此判定是平方時(shí)間復(fù)雜度。但如果選擇鏈表進(jìn)行儲(chǔ)存，則有以下時(shí)間復(fù)雜度分析：鏈表的每次插入操作的時(shí)間復(fù)雜度為常數(shù)即O（1），所以僅僅需要操作n次，即線性時(shí)間復(fù)雜度，相較原來(lái)使用數(shù)組，使用鏈表的時(shí)間復(fù)雜度明顯降低了。

3.2 優(yōu)化核心算法

這種情況是針對(duì)于對(duì)于算法設(shè)計(jì)能力不足，從而導(dǎo)致整個(gè)程序的時(shí)間復(fù)雜度增高，這種情況要求編程者需要極高的算法能力。因此，這通過(guò)幾個(gè)簡(jiǎn)單的算法優(yōu)化的例子來(lái)說(shuō)明。

“八皇后”問(wèn)題是算法設(shè)計(jì)領(lǐng)域的經(jīng)典問(wèn)題，題目大意是，有一個(gè)8*8的棋盤，在棋盤上放置8個(gè)棋子（“皇后”）使得它們互不攻擊，即每次放棋子的時(shí)候，需要判斷當(dāng)前的列、行、兩條斜對(duì)角線是否有棋子，如果有則不能放在這個(gè)地方，如果沒(méi)有則可以放在這個(gè)地方，問(wèn)一共有多少種放法？這個(gè)問(wèn)題看起來(lái)實(shí)現(xiàn)不難，我們很容易寫出以下算法：

算法“八皇后”問(wèn)題求解

根據(jù)上面的算法我們?nèi)菀字苯拥玫较旅娴腃語(yǔ)言代碼：

程序1 算法1的C語(yǔ)言實(shí)現(xiàn)（未剪枝）

if（check（））//check方法檢查當(dāng)前棋盤是否符合題目要求

但按照如上方式編寫的代碼時(shí)間復(fù)雜度很高，因?yàn)榇顺绦驎?huì)將每一種情況列舉出來(lái)，然后逐個(gè)判斷每種情況下的棋盤是否符合要求，由于棋盤是8*8布局，因此一共有88種可能，因此這樣的算法時(shí)間復(fù)雜度是相當(dāng)高的，所以我們需要優(yōu)化算法。類似程序1的遞歸搜索算法，常使用“剪枝”方法進(jìn)行優(yōu)化。類似上面的算法，每次遞歸到某一層，也許當(dāng)前層的狀態(tài)已經(jīng)不符合題目要求了，再怎么擴(kuò)展也不可能比當(dāng)前情況更優(yōu)，沒(méi)必要繼續(xù)向下搜索了，就應(yīng)當(dāng)強(qiáng)制把它“剪”掉，就像園丁在花園里為樹修剪枝葉一樣，就可以直接返回結(jié)果，此即為剪枝的思想。因此將此程序進(jìn)行剪枝，如下：

程序2 算法1的C語(yǔ)言實(shí)現(xiàn)（剪枝后）

在處理復(fù)雜算法時(shí)，一定要從整體把握算法的效率，要在適當(dāng)?shù)奈恢眠M(jìn)行剪枝，否則時(shí)間復(fù)雜度將會(huì)以指數(shù)級(jí)別增加。

3.3 犧牲空間復(fù)雜度

編程人員有時(shí)會(huì)修改某些數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以節(jié)省硬盤存儲(chǔ)空間，但是缺點(diǎn)顯而易見(jiàn)，這樣做會(huì)導(dǎo)致運(yùn)算量增大，會(huì)增加時(shí)間的復(fù)雜度。事實(shí)上計(jì)算機(jī)誕生初期其儲(chǔ)存空間很小，于是人們會(huì)花費(fèi)更多的時(shí)間來(lái)尋找更好的算法以處理數(shù)據(jù)，例如增加一些時(shí)間的復(fù)雜度來(lái)減少空間的復(fù)雜度。一個(gè)具體的例子是，假設(shè)存在一個(gè)搜索算法可實(shí)現(xiàn)這樣的功能，每搜索到一種新情況，即將當(dāng)前情況保存下來(lái)。為此，常見(jiàn)的思路是開(kāi)辟一個(gè)隊(duì)列以存儲(chǔ)數(shù)據(jù)且節(jié)省存儲(chǔ)空間，每搜到一種新情況，即令這個(gè)新的情況入隊(duì)。但是運(yùn)用隊(duì)列存儲(chǔ)時(shí)，每次查找過(guò)程中需要判斷已存儲(chǔ)情況與搜索到的新情況是否相同的時(shí)候，需要枚舉整個(gè)隊(duì)列，顯然，此種操作時(shí)間復(fù)雜度會(huì)很高，但是空間復(fù)雜度很低。因此為優(yōu)化時(shí)間，可以選擇犧牲空間。仍以上述情況為例，可以開(kāi)辟一個(gè)多維數(shù)組，每一維都表示情況中的某個(gè)條件，這樣做雖然會(huì)增加很大的空間復(fù)雜度，但是每次儲(chǔ)存和判斷相同情況的時(shí)間復(fù)雜度都是常數(shù)階的，即可節(jié)省大量時(shí)間。

對(duì)于犧牲空間復(fù)雜度的方法，更多的需要結(jié)合具體情況?，F(xiàn)時(shí)計(jì)算機(jī)硬盤儲(chǔ)存容量通常很大，故編程人員可以選擇犧牲空間來(lái)優(yōu)化程序運(yùn)行的時(shí)間。通?？梢誀奚臻g的幾種情況如下：大量數(shù)據(jù)需要判斷相等的情況、動(dòng)態(tài)規(guī)劃問(wèn)題利用數(shù)組來(lái)壓縮轉(zhuǎn)移方程、區(qū)間數(shù)組內(nèi)容的在線修改與查詢等，這些問(wèn)題涵蓋了常見(jiàn)的幾種需要犧牲空間來(lái)優(yōu)化時(shí)間的算法。另舉一個(gè)具體的例子以展示犧牲空間復(fù)雜度方法，現(xiàn)有一種二維的魔方，有三種操作方式，求最少需要多少次操作可以達(dá)到某種特定的目標(biāo)狀態(tài)。此為經(jīng)典的廣度優(yōu)先搜索的實(shí)例，容易想到開(kāi)辟一個(gè)隊(duì)列用來(lái)存放我們已經(jīng)搜索過(guò)的情況，但是在當(dāng)前情況入隊(duì)判斷的時(shí)候就會(huì)遇到本文之前討論的問(wèn)題，即判斷代價(jià)太大，每次枚舉隊(duì)列方式不符合優(yōu)化時(shí)間復(fù)雜度的需要。觀察可知，二維魔方只有六個(gè)格子，每個(gè)格子只有三個(gè)狀態(tài)，由于狀態(tài)量比較小，所以我們可以合理的犧牲空間，故可以開(kāi)辟一個(gè)六維數(shù)組，每維數(shù)組的長(zhǎng)度為3，這樣整個(gè)空間大小為3的6次方，這樣我們就可以利用常數(shù)時(shí)間復(fù)雜度來(lái)處理上述情況，大幅度優(yōu)化了時(shí)間復(fù)雜度。

4 結(jié)束語(yǔ)

上面介紹了有關(guān)時(shí)間復(fù)雜度優(yōu)化的幾種方式，但在真正的程序開(kāi)發(fā)過(guò)程中，優(yōu)化時(shí)間復(fù)雜度的方法遠(yuǎn)遠(yuǎn)不止三種。更多的優(yōu)化方案還需要來(lái)源于日常學(xué)習(xí)以及實(shí)際開(kāi)發(fā)中的經(jīng)驗(yàn)積累，只有熟練的掌握各種算法，才能在時(shí)間復(fù)雜度優(yōu)化方面表現(xiàn)的更出色。現(xiàn)代的計(jì)算機(jī)配置逐漸走高，時(shí)間復(fù)雜度優(yōu)化看似小事，但在程序底層操作時(shí)，算法的時(shí)間復(fù)雜度優(yōu)化才真正體現(xiàn)出其意義。