1 算法與時間復雜度

算法（Algorithm）是求解一個問題需要遵循的，被清楚指定的簡單指令的集合。
算法一旦確定，那么下一步就要確定該算法將需要多少時間和空間等資源，如果一個算法需要一兩年的時間來完成，那么該算法的用處就不會太大。同樣如果該算法需要若干個GB的內存，那么在大部分機器上都無法使用。

一個算法的評價主要從時間復雜度和空間復雜度來考慮。

而時間復雜度是一個函數，定性描述該算法的運行時間，通常用大O符號表示。

常見的時間復雜度有O(1),O(logn),O(n),O(n^2),O(2^n)...等

那么一個算法的時間復雜度如何計算呢，下面接著講。

2 時間復雜度計算

2.1 第一個時間復雜度計算

首先我們定義算法中的語句執行次數稱為語句頻度或時間頻度為T(n)。即T(n)表示程序的執行次數 。

首先我們看看如下的方法1執行多少次；

public int method1(){
     System.out.println("java技術指北 等你來"); //執行1次
     return 0;          //執行1次
 }

沒錯，它內部一共執行2次。

那么我們來看下面的方法2執行幾次：

public int method2(int n){
        for(int i = 0; i< n ; i++){
         //i = 0 執行1次，i< n 執行n+1次，i++執行n次
            System.out.println("java技術指北 等你來"); //輸出語句執行n次
        }
        return 1; //return 執行一次
    }

對，它一共執行了 3n+3 次。

那么對于方法1就有 T(n) = 2;
對于方法2就有 T(n) = 3n + 3;

實際的代碼肯定比示例中的代碼復雜得多，去統計代碼的執行次數顯然不可能，所以算法一般使用T(n)的漸進估算值來反映代碼的執行速度。而這個估算值我們用"時間復雜度"來表示。

所以針對方法1和方法2，如何根據T(n)估算出時間復雜度
過程如下：

1. 對于 T(n) = 2 ，由于T(n)是一個常數，那么時間復雜度可以直接估算為 1 。所以T(n) = 2 的時間復雜度為 1。用標準的時間復雜度函數表示就是 O(1)。
2. 對于T(n) = 3n + 3 ，隨著n值得不斷增長，常數3相對于3n來說可以忽略不計。而系數一般也會估算成1。相當于去掉了系數和常數，則該時間復雜度為n。用時間復雜度函數表示就是O(n)。
3. 依次推廣到如下多項式中：對于T(n) = 3n^2 + 3n + 3. 隨著n值得不斷增大，多項式后面的項的增長就遠沒有n^2的增長大，可以直接舍棄低階項和常數項，則只保留n的次方數最大的那一項，所以它的時間復雜度就為O(n^3)。

小結一下，以上三個表達式的時間復雜度表示如下

總結以上規律：

• T(n)是常數：時間復雜度為O(1)
• T(n)不是常數：時間復雜度為O(T(n)的最高次項并且去掉最高次項的系數)

2.2 常見循環的復雜度

下面方法1的時間復雜度為 O(1):

//時間復雜度為 O(1)
    public void m1(){
        System.out.println("java技術指北 等你來");
        System.out.println("操千曲而后曉聲，觀千劍而后識器");
        ...
        System.out.println("java技術指北 非你莫屬");
    }

下面方法2的時間復雜度為 O(n):

//時間復雜度為 O(n)    
    public int method2(int n){
        for(int i = 0; i < n ; i++){
            System.out.println("java技術指北 等你來");
        }
        return 1;
    }

下面方法3 時間復雜度為 O(n^2):

//時間復雜度為 O(n^2)
    public void method3(int n){
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < i ; j ++){
                System.out.println("java技術指北 等你來");
            }
        }
    }

下面方法4的時間復雜度為 O(n^2)：
以下方法4中第一個循環執行Q其時間復雜度為為O(n^2)
第二個循環時間復雜度為O(n)
則整個方法的時間復雜度要舍棄變化小的部分，最終的時間復雜度為O(n^2)

//時間復雜度為 O(n^2) 
    public int method4(int n){
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < i ; j ++){
                System.out.println("java技術指北 等你來");
            }
        }
        for(int i = 0; i < n ; i++){
            System.out.println("java技術指北 等你來");
        }
        return 1;
    }

方法5的時間復雜度依然為O(n):
由于隨著n的增大，方法5種執行次數最多的是else后面的循環，所以會取執行次數最多的部分來計算時間復雜度。

//時間復雜度為O(n)
    public int method5(int n){
        if( n < 100){
            for(int i = 0; i < n ; i++){
                for(int j = 0 ; j < n ; j ++){
                    System.out.println("java技術指北 等你來");
                }
            }
        }else{
            for(int i = 0; i < n ; i++){
                System.out.println("java技術指北 等你來");
            }
        }
        return 1;
    }

2.3 其他時間復雜度計算

分析下面方法6的時間復雜度

public void method6(int n){
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < n ; j ++){
                System.out.println("java技術指北 等你來");
            }
        }
    }

方法6執行分析
i=0 輸出語句執行 n 次
i=1 輸出語句執行 n-1 次
i=2 輸出語句執行 n-2 次
...
...
i=n-2 輸出語句執行 2 次
i=n-1 輸出語句執行 1 次

總執行次數就是
T(n) = n + (n-1) + (n-2) ... + 2 + 1
= n(n+1)/2 = 1/2*n^2 =

則其時間復雜度為O(n^2)

下面我們在看方法7的時間復雜度

public void method7(int n){
        int i = 1;
  while(i< n)
  {
      i = i * 2;
  }
    }

執行情況分析：
n = 2 的時候執行1次 即 T(2) = 1
n = 4 的時候執行2次 即 T(4) = 2
n = 8 的時候執行3次 即 T(8) = 3
n = 16 的時候執行4次 即 T(16) = 4

我們發現如下規律
n = 2 的時候有 2^T(2) = 2
n = 4 的時候有 2^T(4) = 4
n = 8 的時候有 2^T(8) = 8
n = 16 的時候有 2^T(16) = 16
n = 32 的時候有 2^T(32) = 32
n = n 的時候有 2^T(n) = n

如果要把T(n)放到等式左邊那么

那么時間復雜度就是

再去掉底數2 則時間復雜度為

3 時間復雜度排序

我們分析了以上幾種簡單循環的時間復雜度，那么既然時間復雜度是用來表示算法的執行效率的，我們對一般常見的時間復雜度進行如下排序(由快到慢)。

timeComplexitiesOrder.jpg

我們再用曲線圖看一下時間復雜度。

從圖中也可以看出，隨著元素變多，指數、階乘級別的增長是最快的。顯而易見其執行效率最低。

4 時間復雜度推算

最后我們計算一下如下遞推關系的算法的時間復雜度
T（n）= T(n-1) + n,其中 T(0) = 1，求T(n)的時間復雜度？

我們可以將n-1 帶入上面的公式，得到 T(n-1) = T（n-2） + (n-1)
再將T(n-1) 的表達式帶入到T(n)的表達式
再依次將n-2 ,n-3...帶入到公式中，其演算結果如下。

T（n）= T(n-1) + n
= T（n-2） + (n-1) + n
= T（n-3） +(n-2) + (n-1) + n
......
= T（2） + 3 + ......(n-2) + (n-1) + n
= T（1） + 2 + 3 + ......(n-2) + (n-1) + n
= T（0） + 1 + 2 + 3 + ......(n-2) + (n-1) + n
= 1 + 1 + 2 + 3 + ...... + (n-1) +n

最終我們得到T(n) 的時間復雜度為O(n^2)

總結

本篇介紹了時間復雜度以及如何計算時間復雜度，相信你已經掌握了吧。