演算法（一）時間複雜度

07-06

演算法（一）時間複雜度

來自專欄集錄

演算法（一）時間複雜度

前言

演算法很重要，但是一般情況下做移動開發並不經常用到，所以很多同學早就將演算法打了個大禮包送還給了老師了，況且很多同學並沒有學習過演算法。這個系列就讓對演算法頭疼的同學能快速的掌握基本的演算法。過年放假階段玩了會遊戲NBA2K17的生涯模式，沒有比賽的日子也都是訓練，而且這些訓練都是自發的，沒有人逼你，從早上練到晚上，屬性也不漲，但是如果日積月累，不訓練和訓練的人的屬性值就會產生較大差距。這個突然讓我意識到了現實世界，要想成為一個球星（技術大牛）那就需要日積月累的刻意訓練，索性放下遊戲，接著寫文章吧。

1.演算法的效率

雖然計算機能快速的完成運算處理，但實際上，它也需要根據輸入數據的大小和演算法效率來消耗一定的處理器資源。要想編寫出能高效運行的程序，我們就需要考慮到演算法的效率。

演算法的效率主要由以下兩個複雜度來評估：

時間複雜度：評估執行程序所需的時間。可以估算出程序對處理器的使用程度。

空間複雜度：評估執行程序所需的存儲空間。可以估算出程序對計算機內存的使用程度。

設計演算法時，一般是要先考慮系統環境，然後權衡時間複雜度和空間複雜度，選取一個平衡點。不過，時間複雜度要比空間複雜度更容易產生問題，因此演算法研究的主要也是時間複雜度，不特別說明的情況下，複雜度就是指時間複雜度。

2.時間複雜度

時間頻度

一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

時間複雜度

前面提到的時間頻度T(n)中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律，為此我們引入時間複雜度的概念。一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數，記作T(n)=O(f(n))，它稱為演算法的漸進時間複雜度，簡稱時間複雜度。

3.大O表示法

像前面用O( )來體現演算法時間複雜度的記法，我們稱之為大O表示法。

演算法複雜度可以從最理想情況、平均情況和最壞情況三個角度來評估，由於平均情況大多和最壞情況持平，而且評估最壞情況也可以避免後顧之憂，因此一般情況下，我們設計演算法時都要直接估算最壞情況的複雜度。

大O表示法O(f(n)中的f(n)的值可以為1、n、logn、n2等，因此我們可以將O(1)、O(n)、O(logn)、O(n2)分別可以稱為常數階、線性階、對數階和平方階，那麼如何推導出f(n)的值呢？我們接著來看推導大O階的方法。

推導大O階

推導大O階，我們可以按照如下的規則來進行推導，得到的結果就是大O表示法：

1.用常數1來取代運行時間中所有加法常數。

2.修改後的運行次數函數中，只保留最高階項

3.如果最高階項存在且不是1，則去除與這個項相乘的常數。

常數階

先舉了例子，如下所示。

int sum = 0,n = 100; //執行一次 sum = (1+n)*n/2; //執行一次 System.out.println (sum); //執行一次

上面演算法的運行的次數的函數為f(n)=3，根據推導大O階的規則1，我們需要將常數3改為1，則這個演算法的時間複雜度為O(1)。如果sum = （1+n）*n/2這條語句再執行10遍，因為這與問題大小n的值並沒有關係，所以這個演算法的時間複雜度仍舊是O(1)，我們可以稱之為常數階。

線性階

線性階主要要分析循環結構的運行情況，如下所示。

for(int i=0;i<n;i++){//時間複雜度為O(1)的演算法...}

上面演算法循環體中的代碼執行了n次，因此時間複雜度為O(n)。

對數階

接著看如下代碼：

int number=1;while(number<n){number=number*2;//時間複雜度為O(1)的演算法...}

可以看出上面的代碼，隨著number每次乘以2後，都會越來越接近n，當number不小於n時就會退出循環。假設循環的次數為X，則由2^x=n得出x=log?n，因此得出這個演算法的時間複雜度為O(logn)。

平方階

下面的代碼是循環嵌套：

for(int i=0;i<n;i++){ for(int j=0;j<n;i++){ //複雜度為O(1)的演算法 ... } }

內層循環的時間複雜度在講到線性階時就已經得知是O(n)，現在經過外層循環n次，那麼這段演算法的時間複雜度則為O(n2)。

接下來我們來算一下下面演算法的時間複雜度：

for(int i=0;i<n;i++){ for(int j=i;j<n;i++){ //複雜度為O(1)的演算法 ... } }

需要注意的是內循環中int j=i，而不是int j=0。當i=0時，內循環執行了n次；i=1時內循環執行了n-1次，當i=n-1時執行了1次，我們可以推算出總的執行次數為：

n+(n-1)+(n-2)+(n-3)+……+1

=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……

=(n+1)+(n+1)+(n+1)+(n+1)+……

=(n+1)n/2

=n(n+1)/2

=n2/2+n/2

根據此前講過的推導大O階的規則的第二條：只保留最高階，因此保留n2/2。根據第三條去掉和這個項的常數，則去掉1/2,最終這段代碼的時間複雜度為O(n2)。

其他常見複雜度

除了常數階、線性階、平方階、對數階，還有如下時間複雜度：

- f(n)=nlogn時，時間複雜度為O(nlogn)，可以稱為nlogn階。

- f(n)=n3時，時間複雜度為O(n3)，可以稱為立方階。

- f(n)=2?時，時間複雜度為O(2?)，可以稱為指數階。

- f(n)=n!時，時間複雜度為O(n!)，可以稱為階乘階。

- f(n)=(√n時，時間複雜度為O(√n)，可以稱為平方根階。

4.複雜度的比較

下面將演算法中常見的f(n)值根據幾種典型的數量級來列成一張表，根據這種表，我們來看看各種演算法複雜度的差異。

|n |logn| √n| nlogn |n2| 2? |n!|

|---|---|---| ---|---|---|---|

|5 |2 |2 |10 |25 |32 |120|

|10 |3| 3| |30 |100 |1024 |3628800|

|50 |5 |7 |250 |2500 |約10^15 |約3.010^64|

|100 |6 |10 |600 |10000 |約10^30 |約9.310^157|

|1000 |9 |31 |9000 |1000 000 |約10^300 |約4.0*10^2567|

從上表可以看出，O(n)、O(logn)、O(√n )、O(nlogn )隨著n的增加，複雜度提升不大，因此這些複雜度屬於效率高的演算法，反觀O(2?)和O(n!)當n增加到50時，複雜度就突破十位數了，這種效率極差的複雜度最好不要出現在程序中，因此在動手編程時要評估所寫演算法的最壞情況的複雜度。

下面給出一個更加直觀的圖：

這裡寫圖片描述

其中x軸代表n值，y軸代表T(n)值（時間複雜度）。T(n)值隨著n的值的變化而變化，其中可以看出O(n!)和O(2?)隨著n值的增大，它們的T(n)值上升幅度非常大，而O(logn)、O(n)、O(nlogn)隨著n值的增大，T(n)值上升幅度則很小。

常用的時間複雜度按照耗費的時間從小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)