公眾號：原與譯

我們先來看一到算法題

給定一個自然數(shù) n，然后求出前 n 個自然數(shù)的和 sum。( n > 0 )

如：</br>
n = 3，則 sum = 1 + 2 + 3 = 6</br>
n = 5，則 sum = 1 + 2 + 3 + 4 + 5 = 15

然后給出如下三種解法。

方法一

private int fun1(int n) {
  return n * (n - 1) / 2;
}

方法二

private static int fun2(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum = sum + i;
    }
    return sum;
}

方法三

private static int fun3(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            sum++;
        }
    }
    return sum;
}

上述給出的三種方法都可滿足給定的需求，但是如果需要在這三個方法中選出一個最優(yōu)解，那就需要使用時間復雜度來衡量他們了。

如果某些行代碼執(zhí)行的時間不受用戶輸入影響，將該代碼的執(zhí)行時間記錄為 常數(shù)時間，用 C 表示

在 fun1 中，方法體就一行代碼。且該行代碼的執(zhí)行時間不受用戶輸入影響，即使入參 n 的值為 1000，10000.... fun1 的執(zhí)行時間依然不變。所以可以把 fun1 的時間復雜度記為 C。

在 fun2 中，是有一些局部變量和一個 for 循環(huán)組成，int sum = 0; int i = 0; return sum; 這些代碼并不會受輸入參數(shù) n 的影響，所以我們記錄為 3C。而 for 循環(huán)中的條件判斷，和 for 循環(huán)中的方法體都會執(zhí)行 n 次（受入參 n 的影響），這部分的時間記錄為 2n。所以 fun2 最后的時間復雜度為 3C + 2n。

在 fun3 是有一些局部變量和兩個 for 循環(huán)構成，且這兩個 for 循環(huán)是嵌套關系。外層 for 循環(huán)的時間復雜度為 n，內存 for 循環(huán)加上循環(huán)體的執(zhí)行的之間復雜度為 2n。對于這中嵌套關系的循環(huán)，復雜度之間是相乘的。及 n * 2n = 2n2。再加上 3 個變量的聲明的事件復雜度 3C。所以 fun3 的漸進時間復雜度為 2n2 + 3C。

通常，在評估時間復雜度的時候，我們會忽略掉兩個部分，一個部分是低階，另一個部分是 常數(shù)階。因為一般在評估時間復雜度的時候都是評估的最壞的時間復雜度，所以這兩部分可以直接忽略掉。對應到上述三個方法中:

fun1 = C = O(1)
fun2 = 3C + 2n = O(n)
fun3 = 2n2 + 3C = O(n2)

如果 for 循環(huán)中是簡單的線性增加（減少）且其上限不是一個常數(shù)的情況下，那么可以認為當前的循環(huán)的時間復雜度為 O(n)

public void method1(int n){
    for(int i = 0; i < n; i++){
        // do O(1)
    }
} 

上述方法 method1 中的 for 循環(huán)的時間復雜就是 O(n)。

public void method2(int n) {
    for(int i = 0; i < 10000; i++) {
        // do O(1)
    }
}

此時，method2 方法中也有一個 for 循環(huán)，但是這個循環(huán)的執(zhí)行時間并不受輸入參數(shù) n 的影響，所以，method2 的時間復雜度為 O(1)。

知道了上述三個方法的漸進時間復雜度，下面來看看他們的增長順序：

假設有 f(n) = 2n2 + n + 6 ; g(n) = 100n + 3，那么忽略完它們的低階及常數(shù)階之后則 f(n) = n2，g(n) = n。
由此我們可以判斷 f(n) 的增長順序是要高于 g(n) 的。也就是 f(n) 的時間復雜度比 g(n) 要高。

下面是上述是三種方法各自時間復雜度的圖示：

橫坐標 n 表示用戶輸入的數(shù)據量
縱坐標 t 表示計算消耗的時間

從圖可以看出，增長順序由低到高為 O(1) < O(n) < O(n2)。算法的性能排序是 fun1 > fun2 > fun3。

幾種表示復雜度的漸進符號
我們在上面表示算法的復雜度時候用的漸進符號是大 O 符號，其實還有兩種漸進符號表示復雜度的，它們分別是 Θ 和 Ω 符號 。

O 漸進符號定義了一個算法的上限，也就是我們說的最壞時間復雜度。例如，插入排序，最佳的情況下的時間復雜度是 O(n)，而最壞的情況是 O(n2)，所以我們可以說插入排序的事件復雜度是 O(n2)

Θ 漸進符號表示的是一個算法從上線到下限的時間復雜度。一個簡單的方法獲取 Θ 漸進表達式為去掉低階以及忽略常數(shù)階。例如：3n3 + 6n2 + 6000 = Θ(n3)，而如果使用Θ表示插入排序的事件復雜度，則需要如下：

1. 插入排序的最壞時間復雜度為 Θ(n2)
2. 插入排序的最佳時間復雜度為 Θ(n)

Ω 漸進符號表示一個算法的下限，也就是我們說的最佳時間復雜度。如果我們需要就拿一個算法的最佳時間復雜度的時候，Ω會被用到。Ω 符號是這三個漸進符號中使用最少的。

下面我們來分下各種循環(huán)的時間復雜度。

O(1): 如果一個方法或者語句中不包含循環(huán)，遞歸，或者沒有調用其他時間復雜度為非常數(shù)的情況下，這個方法的時間復雜度被認為是 O(1)。 注意，一個循環(huán)或者遞歸如果執(zhí)行的次數(shù)為常數(shù)級。則它們的時間復雜度依然被認為是 O(1)，如下代碼中的循環(huán)就是 O(1)：

int c = 100;
for (int i = 1; i <= c; i++){
    // 執(zhí)行 O(1) 的循環(huán)體
}

O(n): 如果循環(huán)是以一個恒定的值遞增/遞減，則循環(huán)的時間復雜度就可以記為 O(n)

c 是一個常數(shù)；n 為用戶輸入

for (int i = 0; i < n; i = i+c){
    // do O(1)
}

上述 for 循環(huán)中，n 是用戶輸入，c 是一個常量，我們假設 n = 10; c = 2; 變量 i 的值依次遞增為：0，2，4，6，8；執(zhí)行次數(shù)為 n/c；記為 O(n/c)，最后忽略掉常數(shù)階c，則為 O(n)。

O(n2)：如果一個方法中包含兩個嵌套關系的循環(huán)，且循環(huán)里面的循環(huán)變量都是以一個恒定的值遞增/遞減。那么這個方法的時間復雜度可以記為 O(n2)，如下：

// n 表示用戶輸入；c 表示常數(shù)
for (int i = 1; i <= n; i += c) {
    for (int k = 1; k <= n; k += c) {
        // do O(1)
    }
}

O(Logn): 如果循環(huán)中的循環(huán)變量除以/乘以 一個常數(shù)，那么該循環(huán)的事件復雜度可以記為 O(Logn)

// n 表示用戶輸入；c 表示常數(shù)
for (int i = 0; i <= n; i *= c) {
    // do O(1)
}

我們假設 n = 32; c = 2；則循環(huán)變量 i 的值依次為：0，2，4，8，16，32 ......

我們可以把 i 的值記為 1 , C , C2 , C3 ...... C^k-1

接著就是 C^k-1 <= n，我們求出 k 的值，這里是一個對數(shù)運算，算出來就是 k < Logc^n+1 (Log 以 C 為底 n+1 的對數(shù))，接著我們忽略掉 Logc^n+1 中的常數(shù)階 c 和 1。最終的結果就是 Logn。

對數(shù)計算小常識：
假設 a^x = N ，我們知道 a = 2，x = 3, 那么 N 就等于 8，這是一個指數(shù)運算，求的是 N
對數(shù)運算就是已知 a 和 N 求 x，如 2^x = 8, 我們一眼就能看出 x = 3。寫作 x = Log2^8 (Log 以 2 為底 8 的對數(shù))

例如，二分查找的時間復雜度就是 O(Logn)

O(LogLogn): 如果一個 for 循環(huán)中的循環(huán)變按照指數(shù)級的遞增或者遞減，那么，這個循環(huán)的事件負責度可以記為 O(LogLogn)。

// n 表示用戶輸入；c 表示常數(shù)
// pow 表示 i^c
for (int i = 2; i < n; i = Math.pow(i, c)) {
    // do O(1)
}

上述代碼中，循環(huán)變量 i 的初始值為 2，i 的值變化如下及循環(huán)的時間復雜度計算如下：

我們最終忽略低階及常數(shù)階之后得到的漸進時間復雜度為 O(LogLogn)

O(nLogn): 下面我們來看一個漸進時間復雜度為 O(nLogn) 的例子。

public void fun(int n) {
    for (int i = 0; i < n; i++ ){
        for (int k = 1; k < n; k = k*2){
            // do O(1)
        }
    }
}

上述方法 fun 中，包含了兩個嵌套的 for 循環(huán)，外層 for 循環(huán)的事件復雜度為 O(n); 內層 for 循環(huán)的事件復雜度為 O(logn)。
**
在計算嵌套 for 循環(huán)的時候，需要將每一層的時間復雜度相乘。則有：O(n) * O(logn)，所以上述方法 fun 的漸進時間復雜度為O(nlogn)。

下面看幾個例子

public void demo1(int n) {
    for (int i = 0; i < n; i++) {
        // do O(1)
    }
    
    for (int i = 1; i < n; i = i * 2) {
        // do O(1)
    }
    
    for (int i = 0; i < 100; i++) {
        // do O(1)
    }
}

上述方法 demo1 中，包含了三個并列的 for 循環(huán)，現(xiàn)在我們很容易就能判斷出第一個 for 循環(huán)的時間復雜度為 O(n); 第二個 for 循環(huán)的時間復雜度為 O(logn); 而第三個 for 循環(huán)的時間復雜度為 O(1), 因為它的執(zhí)行次數(shù)并不受用戶輸入的影響。

對于并列的 for 循環(huán)，我們需要把每個 for 循環(huán)的時間復雜度相加，所以方法 demo1的事件復雜度為：O(n) + O(logn) + O(1) 。

那么我們忽略掉低階 O(logn) 和常數(shù)階 O(1)，最后得出方法 demo1的時間復雜度為 O(n)。

public void demo2(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j = j * 2){
            // do O(1)
        }
    }
    
    for (int i = 0; i < n; i++) {
        for(int j = 1; j < n; j++) {
            // do O(1)
        }
    }
}

分析：demo2 中，有兩個并列型大的 for 循環(huán)，每一個 for 循環(huán)都是一個嵌套型的循環(huán)。第一個大的 for 循環(huán)的時間復雜度為 O(nlogn)；第二個大的 for 循環(huán)的時間復雜度為 O(n2)。demo2 的時間復雜度為 f(n) = O(nlogn) + O(n2) 。省略低階 O(nlogn) 之后，demo2 的漸進時間復雜度為 O(n2)。

注意：對于一個方法中包含多個 for 循環(huán)的情況，如果它們是并列的，則該方法的時間復雜度為多個 for 循環(huán)的時間復雜度的和；
如果是嵌套的，則該方法的時間復雜度為多個 for 循環(huán)的時間復雜度的乘積。

下面再看一個例子

// c 表示一個常數(shù)
public void demo3(int m, int n) {
    for(int i = 1; i <= m; i += c) {
        // do O(1)
    }
    
    for(int i = 1; i <= n; i += c) {
        // do O(1)
    }
}

對于 demo3 中，它的時間復雜度為 f(n) = O(m) + O(n) = O(m + n)；如果 m == n，則 f(n) = O(2n) = O(n)。

好了，上面分別講述了 O(1), O(n), O(n2)，O(logn), O(nlogn) 等情況，如有錯誤，還望指出。