1 算法與時間復(fù)雜度

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

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

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

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

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

2 時間復(fù)雜度計算

2.1 第一個時間復(fù)雜度計算

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

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

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

沒錯，它內(nèi)部一共執(zhí)行2次。

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

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

對，它一共執(zhí)行了 3n+3 次。

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

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

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

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

小結(jié)一下，以上三個表達(dá)式的時間復(fù)雜度表示如下

總結(jié)以上規(guī)律：

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

2.2 常見循環(huán)的復(fù)雜度

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

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

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

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

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

//時間復(fù)雜度為 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技術(shù)指北 等你來");
            }
        }
    }

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

//時間復(fù)雜度為 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技術(shù)指北 等你來");
            }
        }
        for(int i = 0; i < n ; i++){
            System.out.println("java技術(shù)指北 等你來");
        }
        return 1;
    }

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

//時間復(fù)雜度為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技術(shù)指北 等你來");
                }
            }
        }else{
            for(int i = 0; i < n ; i++){
                System.out.println("java技術(shù)指北 等你來");
            }
        }
        return 1;
    }

2.3 其他時間復(fù)雜度計算

分析下面方法6的時間復(fù)雜度

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

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

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

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

下面我們在看方法7的時間復(fù)雜度

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

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

我們發(fā)現(xiàn)如下規(guī)律
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)放到等式左邊那么

那么時間復(fù)雜度就是

再去掉底數(shù)2 則時間復(fù)雜度為

3 時間復(fù)雜度排序

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

timeComplexitiesOrder.jpg

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

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

4 時間復(fù)雜度推算

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

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

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) 的時間復(fù)雜度為O(n^2)

總結(jié)

本篇介紹了時間復(fù)雜度以及如何計算時間復(fù)雜度，相信你已經(jīng)掌握了吧。