簡要介紹演算法時間複雜度

在接下來的數據結構中，我們將會開始接觸到一些演算法，也就是「解決某個問題的方法」，而解決同一個問題總是會存在不同的演算法，所以我們需要在不同的演算法之中做出抉擇，而做出抉擇的根據往往就是演算法耗費的時間（特殊情形下我們還需要考慮演算法耗費的空間）。因此我們今天就來學習如何簡單的判斷演算法將會耗費的時間。

首先我們知道，同一個演算法或者說同一個程序，在不同的計算機上耗費的時間是不一樣的，因為不同的計算機硬體運算能力會存在不同。此外，在同一台計算機中，不同的操作，如加法和乘法要消耗的時間也會不同，整數加法和浮點數加法消耗的時間也會不同，因為同樣在高級編程語言中只需要一個語句的操作，在計算機語言層面上對應的指令數量、計算機完成的速度也會不同。

但是因為我們希望討論的是「演算法將要耗費的時間」，而不是完全具體情況下程序將要耗費的時間，所以我們計算演算法將要花費的時間時，做不到或者說不應該計算出它具體的時間花費（比如xxx秒）。因此我們計算演算法的時間花費時很重要的一點就是：不考慮某個具體操作要消耗的時間，我們將「一個操作」花費的時間統一記為「一個時間單位」，不論這個操作是a=b+c還是a+=b*c。

接下來我們要明白一個東西，俗稱「大O階」。在討論大O階之前，我們要明白一點：我們計算演算法將花費的時間時，一般都是計算其可能花費的最大時間。為什麼呢？我們假設我們要解決的問題是查找或者排序，那麼不論什麼演算法，在最良好的情況下都可以出現「一查就恰好找到」和「數據本身已經排好序」的情況，而這樣作比較是不能比較出演算法的「優劣」的，我們希望看到的，就是在最壞的情況下各個演算法能夠做出怎樣的速度。所以我們計算演算法消耗的時間，一般都是計算其最壞情況（也有可能計算其平均情況，因為最壞情況下速度不太良好的演算法有可能平均情況下是夠好的）。

現在，我們假設這樣一個演算法：用順序比較（從第一個開始逐一比較）的方法，在一個大小為n的數組中查找指定數據，若存在則返回true，否則返回false。這個演算法的最壞情形顯然是不存在指定數據或指定數據為數組最後一個元素，此時演算法將執行n次比較操作，也就是演算法將耗費n個時間單位。這樣的表述當然沒有問題，但我們希望能夠更簡潔的表達這個意思，該怎麼辦呢？這時候就需要大O階出場了。

不難發現，上述演算法的最壞情形並不是「固定」的，它取決於n的大小，可以說是一個與n相關的函數，因此我們可以考慮將其記為函數形式：O(n)（基本上演算法的最壞情形都不是固定的，而是與數據量有關。因為我們說過演算法是處理數據的，如果不論數據多少，執行的操作都是一樣多，那這部分操作是不是個演算法都不好說）。即O(n)代表著演算法在最壞情形下耗費的時間單位，而這個「O()」就是我們所說的大O階（並不嚴謹，需繼續向下看）。

知道了我們該計算演算法的最壞情形以及什麼是大O階之後，我們現在來試試計算下面這個「演算法」的大O階（關於如何計算一段程序耗費的時間在本文最後簡介）

根據我們之前所說的，任意一個操作（除非這個操作本身是調用一個函數，且該函數花費的時間也與數據有關）均假設花費1個時間單位，上述演算法累計有3*n+3*(n-x)+4*x+3*n+100個操作，簡單化簡的話就是9*n+x+100，由於對數據操作時存在區別對待，所以存在一個不確定的x。

那麼問題來了，我們這時候應該說該演算法的大O階為O(9*n+x+100)嗎？顯然是不應該的，因為如果要將這樣的未知量也算上，也就意味著對於演算法中的每個選擇結構都得設置單獨的未知量，當演算法的選擇結構很多時，計算演算法的時間花費就會很困難。那麼對於這樣的「未知量」我們該如何處理？很簡單，既然大O階要代表演算法的最壞情況，那我們就假設選擇結構永遠是最壞情況，在上述演算法中也就是永遠都是對數據執行4個操作而不是3個。這樣一來，大O階的計算就簡單了一些，3*n+4*n+3*n+100=10n，為O(10*n+100)。

現在我們再來看看大O階中的常數項，乍一看，我們會認為常數項也是計算演算法時間花費時必不可少的，可是如果我們仔細想想我們分析演算法時間花費的根本目的，就會發現，我們在乎的其實是演算法時間花費與數據量n之間的關係。就像前面說的，如果一段程序不論數據量多少都是花費一樣多的時間單位，那麼這段程序算不算演算法都是一個問題。出於這個原因，對於大O階中的常數項，我們總是選擇直接捨棄（不論大小），因此O(10*n+100)又被我們簡化為了O(10*n)

接下來我們再來看看這段「演算法」，試著計算它要花費的時間

不難計算出其耗費的時間單位為n*n即n^2，大O階為O(n^2)。通過對比我們可以發現，不論O(a*n)的係數a有多大，當數據量n大到一定程度之後，O(n^2)總是比O(a*n)要花費更多時間，簡單地說就是n^2的增長率比a*n的要大得多。出於這個原因（以及之前說過的，常數項總是不可避免或者說不是重點考慮的內容），我們對於大O階中的常數係數也採用省略的做法。所以之前我們計算出的O(10*n)在一般情況下我們也就簡記為O(n)。

講到這兒，想必大家已經能夠猜出我們計算大O階最重要的一點是什麼了，那就是「化簡」，儘可能的化簡：

1.去掉常數項

2.去掉常數係數

3.只保留最高次項

因此，假設一個演算法消耗時間單位為3*n^3+n^2+9*n+239，我們也將其最壞情形表示為O(n^3)。顯然的，這時候的大O階已經不能較為精確的反映出演算法要消耗的時間了，只能說反映出了演算法時間「所處的等級」。但是由於在數據量n足夠大的時候，「低等級」（如n^2）的演算法總是會比「高等級」（如n^3）的演算法更快，所以大部分時候我們也只需要在意演算法耗費時間「所在的等級」，這也是我們極度精簡時間單位的原因。

同樣的，由於極度精簡了時間單位，所以大O階我們也不再稱之為「最壞情形下演算法花費的時間」了，而是稱之為演算法的「時間複雜度」。

那麼，常見的演算法都有哪些時間複雜度呢？一般按從快到慢有這麼一些：

O(1)（表示常數時間內完成，與數據量無關），O(logN)（底數不重要，一般為2），O(N)，O(N*logN)，O(N^2)，O(N^3)

我們在日後有可能會見識到相應的演算法。

最後，是關於計算一段代碼耗費的時間單位時的一般法則：

1.循環語句

一次循環的運行時間最多是該循環內語句的運行時間乘以迭代的次數，如

其運行時間為2*n，時間複雜度為O(n)

2.嵌套的循環

首先記住，從裡向外分析循環。嵌套循環總的運行時間為最內部循環語句的運行時間乘以該組所有循環大小的乘積，如

其運行時間為1*n*n，時間複雜度為O(n^2)

3.順序語句

將各個語句的運行時間求和即可，如

其運行時間為n+1*n*n，時間複雜度為O(n^2)

4.選擇語句

選擇語句的運行時間總是不會超過最長運行時間的那種可能，如

其運行時間總是不會超過S1，S2中的最大者加上判斷語句的時間

上述做法很可能使計算出的運行時間偏高，但可以保證演算法不會超過這樣的「最壞情況」。

好了，這篇博文我們就講這些，因為根據不同的需要，我們對程序的時間複雜度計算也會有不同的要求，而且像遞歸這樣的代碼，對其進行時間複雜度分析有時候會有很大困難，所以對於演算法時間複雜度的簡介，到這裡就差不多了。

更多IT精品課程，訪問中公優就業官網：http://xue.ujiuye.com

勤工儉學計劃」，給你一個真正0元學習IT技術的機會！

http://www.ujiuye.com/zt/qgjx/?wt.bd=lsh

找工作太難？不是你不行，我們來幫你！

http://www.ujiuye.com/zt/jyfc/?wt.bd=lsh

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！