算法效率

算法效率是指算法執行的時間，算法執行時間需通過依據該算法編制的程式在計算機上運行時所消耗的時間來度量。

基本介紹

• 中文名：算法效率
• 外文名：algorithm efficiency
• 依據：程式在計算機上運行消耗時間
• 方法：事後統計的方法等
• 類型：算法執行時間
• 使用範圍：電腦程式語言

簡介

定義

算法效率是指算法執行的時間，算法執行時間需通過依據該算法編制的程式在計算機上運行時所消耗的時間來度量。在現在的計算機硬體環境中，比較少需要考慮這個問題了，特別是pc機的編程，記憶體空間越來越大，所以被考慮得也越來越少，不過一個好的程式設計師，都應該對自己的程式有要求，每一個for比別人少一次判斷1000個for就能夠少掉很多的運行時間。所以能夠理解，能夠大概的去運用"效率度量"還是有很大意義的。

度量方法

度量一個程式的執行時間通常有兩種方法：（一）事後統計的方法（二）事前分析估算的方法。

事後統計的方法不利於較大範圍內的算法比較（異地，異時，異境）。

事前分析估算的方法與許多因素有關，包括算法本身選用的策略、問題的規模、書寫程式的語言、編譯產生的機器代碼質量和機器執行指令的速度等。為便於比較算法本身的優劣，應排除其它影響算法效率的因素。從算法中選取一種對於所研究的問題來說是基本操作的原操作，以該基本操作重複執行的次數作為算法的時間量。（原操作在所有該問題的算法中都相同）

度量一個程式運行時間的方式通過時間複雜度和空間複雜度來表征。

上式表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間複雜度，簡稱時間複雜度。

上式表示空間複雜度。空間複雜度可以作為算法所需存儲空間的量度。若額外空間相對於輸入數據量來說是常數，則稱此算法為原地工作。原地工作意思是一個算法需要少量的輔助空間，且其大小不隨問題規模的大小而改變。如果所占空間量依賴於特定的輸入，則除特別指明外，均按最壞情況來分析。

算法的最優、最差和平均效率

最差效率：指當輸入規模為n時，算法的最壞情況下的效率。

最優效率：指當輸入規模為n時，算法在最優情況下的效率。

平均效率：指當輸入規模為n時，算法的平均效率。

大量實踐經驗告訴我們，我們評價一個算法是應該重點考慮最差效率這一點。

提高算法效率的方法

對數據的邏輯結構進行選擇，是構造數學模型一大關鍵，而算法又是用來解決數學模型的。要使算法效率高，首先必須選好數據的邏輯結構。選擇邏輯結構的目的是提高信息的利用效果。在解決問題的過程中，選擇合理的邏輯結構是相當重要的環節。

選擇合理的存儲結構

數據的存儲結構，分為順序存儲結構和鏈式存儲結構。順序存儲結構的特點是藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係；鏈式存儲結構則是藉助指示元素存儲地址的指針表示數據元素之間的邏輯關係。因為兩種存儲結構的不同，導致這兩種存儲結構在具體使用時也分別存在著優點和缺點。 這裡有一個較簡單的例子：我們需要記錄一個n×n的矩陣，矩陣中包含的非0元素為m個。 此時，我們若採用順序存儲結構，就會使用一個n×n的二維數組，將所有數據元素全部記錄下來；若採用鏈式存儲結構，則需要使用一個包含m個結點的鍊表，記錄所有非0的m個數據元素。由這樣兩種不同的記錄方式，我們可以通過對數據的不同操作來分析它們的優點和缺點。

1． 隨機訪問矩陣中任意元素。由於順序結構在物理位置上是相鄰的，所以可以很容易地獲得任意元素的存儲地址，其複雜度為O(1)；對於鏈式結構，由於不具備物理位置相鄰的特點，所以首先必須對整個鍊表進行一次遍歷，尋找需進行訪問的元素的存儲地址，其複雜度為O(m)。此時使用順序結構顯然效率更高。

2． 對所有數據進行遍歷。兩種存儲結構對於這種操作的複雜度是顯而易見的，順序結構的複雜度為O(n2)，鏈式結構為O(m)。由於在一般情況下m要遠小於n2，所以此時鏈式結構的效率要高上許多。除上述兩種操作外，對於其它的操作，這兩種結構都不存在很明顯的優點和缺點，如對鍊表進行刪除或插入操作，在順序結構中可表示為改變相應位置的數據元素。 既然兩種存儲結構對於不同的操作，其效率存在較大的差異，那么我們在確定存儲結構時，必須仔細分析算法中操作的需要，合理地選擇一種能夠“揚長避短”的存儲結構。

存儲結構的選擇包括以下兩種。

一、合理採用順序存儲結構。我們在平常做題時，大多都是使用順序存儲結構對數據進行存儲。究其原因，一方面是出於順序結構操作方便的考慮，另一方面是在程式實現的過程中，使用順序結構相對於鏈式結構更便於對程式進行調試和查找錯誤。因此，大多數人習慣上認為，能夠使用順序結構進行存儲的問題，最“好”採用順序存儲結構。其實，這個所謂的“好”只是一個相對的標準，是建立在以下兩個前提條件之下的：

1． 鏈式結構存儲的結點與順序結構存儲的結點數目相差不大。這種情況下，由於存儲的結點數目比較接近，使用鏈式結構完全不能體現出記錄結點少的優點，並且可能會由於指針操作較慢而降低算法的效率。更有甚者，由於指針自身占用的空間較大，且結點數目較多，因而算法對空間的要求可能根本無法得到滿足。

2． 並非算法效率的瓶頸所在。由於不是算法最費時間的地方，這裡是否進行改進，顯然是不會對整個算法構成太大影響的，若使用鏈式結構反而會顯得操作過於繁瑣。

二、必要時採用鏈式存儲結構。

由於鏈式結構中指針操作確實較繁瑣，並且速度也較慢，調試也不方便，因而大家一般都不太願意用鏈式的存儲結構。但是，這只是一般的觀點，當鏈式結構確實對算法有很大改進時，我們還是不得不進行考慮的。

然而，如果我們採用的是鏈式存儲結構，那么我們需要多少數據，就只會遍歷多少數據，這樣不僅充分發揮了鏈式存儲結構的優點，而且由於不需單獨對某一個數據進行提取，每次都是對所有數據進行判斷，從而避免了鏈式結構的最大缺點。我們使用鏈式存儲結構，雖然沒有降低問題的時間複雜度(鏈式存儲結構在最壞情況下的存儲量與順序存儲結構的存儲量幾乎相同)，但由於體現了前文所述選擇存儲結構時揚長避短的原則，因而算法的效率也大為提高。我們選擇鏈式的存儲結構，雖然操作上可能稍複雜一些，但由於改進了算法的瓶頸，算法的效率自然也今非昔比。由此可見，必要時選擇鏈式結構這一方法，其效果是不容忽視的。

使用直接初始化

與直接初始化對應的是複製初始化，什麼是直接初始化？什麼又是複製初始化？舉個簡單的例子，

ClassTest ct1；ClassTest ct2(ct1);    //直接初始化ClassTest ct3 = ct1;    //複製初始化

那么直接初始化與複製初始化又有什麼不同呢？直接初始化是直接以一個對象來構造另一個對象，如用ct1來構造ct2，複製初始化是先構造一個對象，再把另一個對象值複製給這個對象，如先構造一個對象ct3，再把ct1中的成員變數的值複製給ct3，從這裡，可以看出直接初始化的效率更高一點，而且使用直接初始化還是一個好處，就是對於不能進行複製操作的對象，如流對象，是不能使用賦值初始化的，只能進行直接初始化。可能我說得不太清楚，那么下面就引用一下經典吧！

以下是Primer是的原話：

“當用於類類型對象時，初始化的複製形式和直接形式有所不同：直接初始化直接調用與實參匹配的構造函式，複製初始化總是調用複製構造函式。複製初始化首先使用指定構造函式創建一個臨時對象，然後用複製構造函式將那個臨時對象複製到正在創建的對象”，還有一段這樣說，“通常直接初始化和複製初始化僅在低級別最佳化上存在差異，然而，對於不支持複製的類型，或者使用非explicit構造函式的時候，它們有本質區別：

ifstream file1("filename")://ok:direct initializationifstream file2 = "filename";//error:copy constructor is private

儘量減少值傳遞，多用引用來傳遞參數。

如果參數是int等語言自定義的類型可能能性能的影響還不是很大，但是如果參數是一個類的對象，那么其效率問題就不言而喻了。例如一個判斷兩個字元串是否相等的函式，其聲明如下：

bool Compare（string s1, string s2)bool Compare(string *s1, string *s2)bool Compare(string &s1, string &s2)bool Compare(const string &s1, const string &s2)

其中若使用第一個函式（值傳遞），則在參數傳遞和函式返回時，需要調用string的構造函式和析構函式兩次（即共多調用了四個函式），而其他的三個函式（指針傳遞和引用傳遞）則不需要調用這四個函式。因為指針和引用都不會創建新的對象。如果一個構造一個對象和析構一個對象的開銷是龐大的，這就是會效率造成一定的影響。

然而在很多人的眼中，指針是一個惡夢，使用指針就意味著錯誤，那么就使用引用吧！它與使用普通值傳遞一樣方便直觀，同時具有指針傳遞的高效和能力。因為引用是一個變數的別名，對其操作等同於對實際對象操作，所以當你確定在你的函式是不會或不需要變數參數的值時，就大膽地在聲明的前面加上一個const吧，就如最後的一個函式聲明一樣。

同時加上一個const還有一個好處，就是可以對常量進行引用，若不加上const修飾符，引用是不能引用常量的。

減少除法運算的使用

無論是整數還是浮點數運算，除法都是一件運算速度很慢的指令，在計算機中實現除法是比較複雜的。所以要減少除法運算的次數，下面介紹一些簡單方法來提高效率：

1、通過數學的方法，把除法變為乘法運算，如if(a > b/c),如果a、b、c都是正數，則可寫成if(a*c > b)

2、讓編譯器有最佳化的餘地，如里你要做的運算是int型的n/8的話，寫成（unsigned)n/8有利於編譯器的最佳化。而要讓編譯器有最佳化的餘地，則除數必須為常數，而這也可以用const修飾一個變數來達到目的。

避免使用多重繼承

在C++中，支持多繼承，即一個子類可以有多個父類。書上都會告訴我們，多重繼承的複雜性和使用的困難，並告誡我們不要輕易使用多重繼承。其實多重繼承並不僅僅使程式和代碼變得更加複雜，還會影響程式的運行效率。

這是因為在C++中每個對象都有一個this指針指向對象本身，而C++中類對成員變數的使用是通過this的地址加偏移量來計算的，而在多重繼承的情況下，這個計算會變數更加複雜，從而降低程式的運行效率。而為了解決二義性，而使用虛基類的多重繼承對效率的影響更為嚴重，因為其繼承關係更加複雜和成員變數所屬的父類關係更加複雜。

將小粒度函式聲明為內聯函式

調用函式是需要保護現場，為局部變數分配記憶體，函式結束後還要恢復現場等開銷，而內聯函式則是把它的代碼直接寫到調用函式處，所以不需要這些開銷，但會使程式的原始碼長度變大。

所以若是小粒度的函式，如下面的Max函式，由於不需要調用普通函式的開銷，所以可以提高程式的效率。

int Max(int a, int b){    return a>b?a:b;}