【摘 要】算法效率的高低直接決定一個(gè)算法的好壞，解決一個(gè)實(shí)際問(wèn)題可以設(shè)計(jì)出很多的算法，但是其效率是不一樣的，如在數(shù)組中查找一個(gè)元素，既可以一個(gè)元素一個(gè)元素的遍歷，也可以對(duì)半查找，顯然對(duì)半查找比遍歷快得多，也就是說(shuō)對(duì)半查找的效率要高。設(shè)計(jì)高效率的算法一直是計(jì)算機(jī)科學(xué)領(lǐng)域?qū)W者孜孜不倦的追求，本文將從實(shí)際問(wèn)題入手，探究影響算法執(zhí)行效率的因素，從而提出優(yōu)化措施，總結(jié)優(yōu)化經(jīng)驗(yàn)，進(jìn)而為日后設(shè)計(jì)高效率的算法奠定堅(jiān)實(shí)的理論與實(shí)踐基礎(chǔ)。

【關(guān)鍵詞】算法，效率，優(yōu)化

算法效率通常使用算法的時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量，時(shí)間復(fù)雜度和空間復(fù)雜度又可以統(tǒng)稱為時(shí)空復(fù)雜度。算法的時(shí)間復(fù)雜度關(guān)心算法關(guān)鍵部分代碼的執(zhí)行次數(shù)，如遍歷一個(gè)長(zhǎng)度為N的數(shù)組，那么關(guān)鍵代碼需要執(zhí)行N次，時(shí)間復(fù)雜度就為；算法的空間復(fù)雜度則主要關(guān)心算法運(yùn)行時(shí)所需占用的存儲(chǔ)空間。顯然，一個(gè)好的算法其時(shí)間復(fù)雜度和空間復(fù)雜度都比較小。

一、影響算法效率的因素

影響算法效率的因素有很多，如問(wèn)題的規(guī)模，顯然問(wèn)題規(guī)模越大算法執(zhí)行時(shí)間越長(zhǎng)；實(shí)現(xiàn)算法的編程語(yǔ)言也會(huì)影響算法效率，選擇編譯型語(yǔ)言要比解釋型語(yǔ)言效率高，如選擇使用C語(yǔ)言就要比選擇使用Java語(yǔ)言實(shí)現(xiàn)算法效率高；數(shù)據(jù)結(jié)構(gòu)的選擇，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)可以方便操作，減少空間占用；編譯產(chǎn)生機(jī)器代碼的質(zhì)量，很多編譯器會(huì)在產(chǎn)生機(jī)器代碼時(shí)進(jìn)行優(yōu)化，從而提高算法效率；機(jī)器執(zhí)行指令的速度，機(jī)器執(zhí)行一條指令的速度越快那么算法的效率就越高。

上述影響算法效率的因素，有的可以通過(guò)更加巧妙的算法設(shè)計(jì)來(lái)規(guī)避冗余運(yùn)算來(lái)提高效率，有的可以通過(guò)多核心并行來(lái)提高處理速度從而提高效率，接下來(lái)我們就探討算法中提高效率的設(shè)計(jì)藝術(shù)。

二、提升算法效率的策略

（一） 遞歸轉(zhuǎn)換為非遞歸實(shí)現(xiàn)

遞歸是一種常用的程序編寫方式，它可以把一個(gè)大的復(fù)雜的問(wèn)題轉(zhuǎn)化為較小的相似的問(wèn)題進(jìn)行求解。然而，遞歸是通常過(guò)程或函數(shù)自己調(diào)用自己來(lái)實(shí)現(xiàn)的，它并不是一種高效的算法編寫方式，在調(diào)用過(guò)程中系統(tǒng)需要處理斷點(diǎn)，保存中斷向量等，并且這些操作所以消耗的指令時(shí)間也遠(yuǎn)大于其他的指令開(kāi)銷。因此，實(shí)現(xiàn)算法時(shí)應(yīng)當(dāng)盡量將遞歸部分代碼轉(zhuǎn)換為非遞歸的方式實(shí)現(xiàn)。例如，計(jì)算N的階乘，其遞歸算法可如下方式：

1int F（int n）

2{

3 if （n==1||n==0）

4 return 1；

5 else

6 return n* F（n-1）；

7}

函數(shù)中的第六行代碼調(diào)用函數(shù)自身，實(shí)現(xiàn)遞歸。使用非遞歸算法改寫程序如下：

int F（int n）

{

if （n==0） reurn 1；

int x=1；

for（i=1；i<=n；i++）

x=x*i；

return x；

}

改寫后的程序中取消了函數(shù)調(diào)用自身的代碼，目的是為了減少因系統(tǒng)維護(hù)中斷程序所需要花費(fèi)的開(kāi)銷。此例只是一個(gè)簡(jiǎn)單的示例，通常，將遞歸算法改寫為非遞歸算法時(shí)，需要用到棧來(lái)保存未完成的工作，需要時(shí)再將數(shù)據(jù)從棧中取出，在進(jìn)行轉(zhuǎn)換時(shí)，對(duì)遞歸函數(shù)的實(shí)現(xiàn)過(guò)程進(jìn)行公式遞推就可得出其非遞歸實(shí)現(xiàn)。

（二）設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)

合理的數(shù)據(jù)結(jié)構(gòu)對(duì)算法的性能至關(guān)重要，一個(gè)合理的數(shù)據(jù)結(jié)構(gòu)可以使用算法中對(duì)變量的訪問(wèn)更加便捷，同時(shí)也能減少變量所需的內(nèi)存空間，從而提高算法的效率。例如，對(duì)于稀疏矩陣，如果矩陣中元素較多，那么就應(yīng)該考慮壓縮矩陣的存儲(chǔ)空間，如果直接定義二維數(shù)組來(lái)存儲(chǔ)矩陣，由于稀疏矩陣中存在大量零元素，那么勢(shì)必會(huì)浪費(fèi)大量的存儲(chǔ)空間，此時(shí)可以考慮使用三元組（行號(hào)，列號(hào)，元素值）來(lái)存儲(chǔ)稀疏矩陣，這樣一來(lái)就能極大地壓縮稀疏矩陣所占用的內(nèi)存空間，同時(shí)遍歷矩陣時(shí)也可以減少遍歷次數(shù)，從而提高算法效率。此外，對(duì)于共享變量，通?？梢允褂寐?lián)合體的方式，使多個(gè)變量共享同一段內(nèi)存空間，這是通過(guò)降低算法的空間復(fù)雜度來(lái)提高算法效率的一種方法。

（三）通過(guò)并行計(jì)算降低算法執(zhí)行時(shí)間

通過(guò)并行計(jì)算大幅降低算法執(zhí)行時(shí)間有兩種方式，一是在單機(jī)上多核心之間的并行；二是多機(jī)間的并行。目前，計(jì)算機(jī)硬件設(shè)備更新較快，主流計(jì)算機(jī)大多是雙核心甚至是四核心，同時(shí)，計(jì)算機(jī)軟件發(fā)展迅速，分布式系統(tǒng)日漸流行。然而，大多數(shù)的算法并沒(méi)有針對(duì)多核心計(jì)算機(jī)或是分布式系統(tǒng)進(jìn)行優(yōu)化，依然是串行執(zhí)行。通過(guò)對(duì)算法進(jìn)行分析，將算法分為可并行部分和不可并行部分（即串行部分），將可并行部分分配給同一機(jī)器上不同的核心并行運(yùn)行，或是將可并行部分分配給分布式系統(tǒng)中不同的主機(jī)運(yùn)行，然后將結(jié)果匯總。在分布式系統(tǒng)進(jìn)行并行計(jì)算時(shí)需要權(quán)衡算法的運(yùn)算量和網(wǎng)絡(luò)開(kāi)銷，從而作出一個(gè)合理的分配。

并行計(jì)算的方式并沒(méi)有降低算法的時(shí)間復(fù)雜度，而是通過(guò)并行執(zhí)行的方式減少了算法運(yùn)行所需的時(shí)間，充分利用多核心計(jì)算機(jī)的硬件優(yōu)勢(shì)或是分布是系統(tǒng)的結(jié)構(gòu)優(yōu)勢(shì)來(lái)提高算法的效率。

（四）借鑒已有的高效算法

目前已經(jīng)存在大量公認(rèn)的高效率的算法，我們?cè)谠O(shè)計(jì)自己的算法時(shí)，可以充分借鑒這類算法來(lái)提高自己算法的效率。例如自己的算法中需要進(jìn)行查找操作，這時(shí)就可以直接調(diào)用快速排序或堆排序算法，通過(guò)調(diào)用已有的高效率算法來(lái)改善自己算法的效率。

本文討論了幾種提高算法效率的方式，實(shí)際上設(shè)計(jì)算法是一項(xiàng)高難度的工作，對(duì)設(shè)計(jì)人員的理論基礎(chǔ)和設(shè)計(jì)經(jīng)驗(yàn)要求非常高，因此需要我們繼續(xù)深入研究，不斷推演新的優(yōu)化策略。

參考文獻(xiàn)：

[1]王成，趙金偉，閆桂榮. 基于綜合統(tǒng)計(jì)法的算法效率分析和優(yōu)化.[J].計(jì)算機(jī)工程.2010（22）

[2]童小明.超巨大規(guī)模的數(shù)值排序.[J].電腦編程技巧與維護(hù).2012（19）