計算時間複雜度

原則

在計算時間複雜度時，我們會遵循以下原則：

只考慮最糟的情況
最小的上界
忽略常數
只考慮最高次項

接下來我們會一一介紹這些原則。

最糟的情況

接著請考慮一個問題，給你一個長度為 $n$ 的序列，接著給你 $q$ 個查詢，每個查詢求序列的某一個連續區間 $[l,r]$ 的總和。

首先，如果你已經將前面的章節讀熟，那你應該可以寫出這樣的程式碼：

int n;

cin >> n; // 讀序列長度

int a[n + 1]; // 開陣列

for(int i = 1; i <= n; i++) {
    cin >> a[i]; // 讀入序列
}

cin >> q; // 有 q 個查詢

for (int i = 1; i <= q; i++) {
    int l, r, cnt = 0;
    cin >> l >> r; // 一筆查詢他的左右界
    for (int j = l; j <= r; j++) {
        cnt += a[j]; // 加總，從 l 跑到 r
    }
    cout << cnt << endl;
}

那這個時間複雜度是多少呢，我們可以先想如果只有一個查詢，那要從 $l$ 跑到 $r$ ，最糟的情況就是 $l$ 接近 $1$ ， $r$ 接近 $n$ ，在這個情況中，要做一次查詢會從一個長度為 $n$ 的序列從頭跑到尾，也就是 $O(n)$ ，雖然你可能認為他不會都跑滿，但根據 big-O 的定義這個演算法就是一個查詢 $O(n)$ 。

那因為有 $q$ 個查詢，所以時間複雜度會增加 $q$ 倍，也就是 $O(qn)$ 。

最小的上界

如下面這份程式碼是計算 $n$ 個整數的加總，很容易知道 $O(n)$ 就是這個演算法的時間複雜度，因為他只是對每個數加一次，而 $n$ 個數就會加 $n$ 次。

不過這裡要注意的是，這個 $O(n)$ 是一個最小的上界，也就是說，這個演算法的時間複雜度不會超過 $O(n)$ ，但也有可能是 $O(n^2), O(n!)$ 之類的，不過我們要找的是最小的上界。

int x = 0, y, n;

cin >> n; // 輸入 n

for (int i = 1; i <= n; i++) {
    cin >> y; // 輸入一個數
    x += y; // 加上去
}

cout << x << endl; // 輸出加總

忽略常數

考慮以下這份程式碼：

for (int i = 1; i <= n; i++) {
    cin >> a[i]; // 讀入序列
}

for (int i = 1; i <= n; i++) {
    a[i] *= 2;
}

for (int i = 1; i <= n; i++) {
    a[i] *= 3;
}

思考看看，這個時間複雜度是多少呢？我們可以看到第一個迴圈是 $O(n)$ ，第二個迴圈也是 $O(n)$ ，第三個迴圈是 $O(3n)$ ，也許你會認為這個是 $O(3n)$ ，但因為 Big-O 不考慮常數（那個乘與 3 倍的常數），所以這個時間複雜度實際上是 $O(n)$ 。

只考慮最高次項

接著考慮以下這份程式碼：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        cout << "Hello" << endl;
    }
}

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            cout << "Hello" << endl;
        }
    }
}

這個時間複雜度是多少呢？我們可以看到第一個迴圈是 $O(n^2)$ ，第二個迴圈是 $O(n^3)$ ，或許你會認為這個是 $O(n^2 + n^3)$ ，但因為 Big-O 只考慮最高次項，所以這個時間複雜度實際上是 $O(n^3)$ 。