算法複雜度分析

最近開始通過極客時間王爭老師的 <<數據結構與算法之美>> 專欄重新複習數據結構與算法。打算通過寫博客的方式記錄下自己的學習重點與心得。

複雜度分析主要用于衡量算法的執行效率,其中又分為時間複雜度分析以及空間複雜度分析。

大 O 複雜度表示法

導論

先從簡單的引導開始,理解大 O 是怎麽得出的。

void calculate(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
}

從以上這段程序中我們可以判斷出,第二行執行了 1 單位時間,而第三和第四行分別執行了 $n$ 次(除去 for 循環的初始條件 i = 0 執行了 1 單位時間),所以總共需要 $(2n + 2)$ 個單位時間。

接下來繼續分析:

void calculate(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += (i + j);
        }
    }
}

接著以上套路,這段程序第二行執行了1單位時間,第三行執行了 $n$ 次 (除去 for 循環初始條件 int i = 0 執行了 1 單位時間),需要 $n$ 個單位時間。第四和第五行分別執行了 ${n^2}$ 次 (除去 for 循環初始條件 int j = 0 執行了 $n$ 個單位時間),所以需要 $2n^2$ 個單位時間。總共計算下來,總執行時間為 $T(n) = (2n^2 + 2n + 2) * 單位時間$ 。

接下來,就是怎麽使用大 O 表示法。大 O 的公式如下:
$$
T(n) = O (f(n))
$$
T(n) 表示代碼執行時間,n 表示數據規模,f(n) 表示每行代碼執行的次數總和,而 O 則表示代碼的執行時間 T(n) 與 f(n) 成正比。

大 O 表示法可將以上兩個例子的時間複雜度的寫法簡化為 $T(n) = O(n)$ & $T(n) = O(n^2)$ 。

重點

使用大 O 表示時間複雜度有以下幾個訣竅:

  • 只需要關注循環執行次數最多的那段代碼即可,比如以上列舉的兩個例子中的循環部份代碼。

  • 加法法則: 如果最後計算的是變量相加,則總時間複雜度就等于運算量級最大的那段代碼的時間複雜度。

    Example

    int calculate(int n) {
        int total1 = 0;
        for (int i = 0; i < n; i++) {
            total1 += i;
        }
    
        int total2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                total2 += j;
            }
        }
        return total1 + total2;
    }

    這段代碼的複雜度最終用大 O 表示法為: $O(n^2)$ 。

  • 乘法法則: 嵌套代碼的複雜度等于嵌套內外代碼的乘積。

    Example

    int calculate1(int n) {
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += i + calculate2(i);
        }
        return total
    }
    int calculate2(int n) {
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += i;
        }
        return total;
    }

    這段代碼的複雜度最終用大 O 表示法為 $O(n^2)$ 。

複雜度量級

常見的複雜度量級分別有以下幾種:

  • 常量級: $O(1)$
  • 對數級: $O(logn)$
  • 線性級: $O(n)$
  • 線性對數級: $O(nlogn)$
  • 平方級: $O(n^2)$
  • 立方級: $O(n^3)$
  • x 次方級: $O(n ^ x)$
  • 指數級: $O(2^n)$ -> 非多項式量級
  • 階乘級: $O(n!)$ -> 非多項式量級

非多項式量級的算法問題叫做 NP (Non-Deterministic Polynomial) 問題。

$O(logn)$ & $O(nlogn)$

其中最不好分析的為 $O(logn)$ & $O(nlogn)$ 。在這邊舉個例子幫助理解:

int x = 2;
while (x <= n) {
    x *= 2;
}

這段代碼中的 i 每循環一次就乘 2,當大于 n 時循環結束。由此我們可以得出:
$$
n = 2^x
$$
只要知道 x 值是多少,我們就能知道代碼執行的次數,所以 x 就是我們要求的值:
$$
x = log_{2}n
$$
用大 O 表示時間複雜度就是 $O(log_{2}n)$ 。

$O(m + n)$ & $O(m * n)$

這種形式則是因為代碼的複雜度由兩個數據規模決定,舉例:

int calculate(int m, int n) {
    int total1 = 0;
    for (int i = 0; i < m; i++) {
        total1 += i;
    }

    int total2 = 0;
    for (int i = 0; i < n; i++) {
        total2 += i;
    }

    return total1 + total2;
}

以上代碼由于 m 和 n 都無法預先得知量級是多少,因此時間複雜度用大 O 表示為: $O(m + n)$ 。

空間複雜度分析

空間複雜度分析則比較直接,舉例:

void space(int n) {
    int[] arr = new arr[n];
    for (int i = 0; i < n; i++) {
        arr[n] = i;
    }
}

第二行初始化了一個大小為 n 的 int 類型數組,第四行申請了一個 for 循環的初始條件變量 i,僅占用常量級空間,與數據規模 n 無關。因此,用大 O 表示法表達空間複雜度就為 $O(n)$ 。