4.9 時間複雜度估計與 TLE
競程的題目有時間限制（通常 1-2 秒）。如果你的程式執行得太慢，會得到 TLE（Time Limit Exceeded）。你必須估計程式需要多久。
基本法則：現代電腦能在 1 秒內執行約 10^8 次簡單運算。
「簡單運算」包括加、減、比較。「複雜運算」如除法、取餘會慢一些。
如何估計：
- 計算你的程式會執行多少次運算
- 除以 10^8 得到秒數
- 如果秒數 ≤ 2，通常沒問題
¶範例程式碼
範例 1：估計執行時間
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
int answer = 0;
// 這個迴圈執行 n 次
// 每次執行 3 個運算：answer += n、n--、比較 n > 0
// 總共約 3n 次運算
do {
answer += n;
n--;
} while (n > 0);
cout << answer << "\n";
return 0;
}
複雜度分析：
- 如果 n = 10^7（千萬），總運算次數 ≈ 3 × 10^7 ≈ 0.3 秒 ✓
- 如果 n = 10^8（億），總運算次數 ≈ 3 × 10^8 ≈ 3 秒 ✗ TLE 了！
範例 2：巢狀迴圈的時間複雜度
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 外層迴圈 n 次，內層迴圈 n 次
// 總共 n × n = n^2 次運算
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << i << " " << j << "\n";
}
}
return 0;
}
複雜度分析：
- 如果 n = 10^4（萬），運算次數 = 10^8，約 1 秒 ✓
- 如果 n = 10^5（十萬），運算次數 = 10^10，約 100 秒 ✗ TLE 了！
動手試試看：估計 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { x++; } } 在 n = 10^5 時要花多久。