程序設(shè)計的時間復(fù)雜度優(yōu)化技巧

趙美勇，崔旭冉，宋思睿，湯繼澳，王夢媛

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

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

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

2 常見的幾種時間復(fù)雜度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法“八皇后”問題求解

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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