計算時間複雜度

原則

#

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

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

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

最糟的情況

#

接著請考慮一個問題，給你一個長度為 \(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)\)。