4.9 你的程式會不會太慢？（TLE）

競程的題目有時間限制（通常 1-2 秒）。如果你的程式跑得太慢、超過時限，會得到 TLE（Time Limit Exceeded）。所以在動手寫之前，最好先大概估一下：這個做法會不會太慢？

基本法則：現代電腦能在 1 秒內執行約 10^9 次簡單運算。

「簡單運算」包括加、減、比較。「複雜運算」如除法、取餘會慢一些——複雜運算多、或沒把握時，抓保守一點（例如改用 10^8 估）。

如何估計：

1. 計算你的程式大約會執行多少次運算
2. 除以 10^9，估出秒數的量級
3. 估出來比時限小很多（例如不到十分之一）→ 放心寫；跟時限同一個量級 → 當作危險——換方法，或先實測確認

¶範例程式碼

範例 1：估計執行時間

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long answer = 0;   // 總和會超過 int 範圍（複習 2.9）

    // 這個迴圈執行 n 次
    // 每次執行 3 個運算：answer += n、n--、比較 n > 0
    // 總共約 3n 次運算
    do {
        answer += n;
        n--;
    } while (n > 0);

    cout << answer << "\n";
    return 0;
}

估算：

• 如果 n = 10^7（千萬），總運算次數 \approx 3 \times 10^7，約 0.03 秒 ✓
• 如果 n = 10^9（十億），總運算次數 \approx 3 \times 10^9，約 3 秒 ✗ TLE 了！

範例 2：巢狀迴圈會做多少次運算

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;

    long long count = 0;   // 只做計算、不輸出，估的才是迴圈本身的速度
    // 外層迴圈 n 次，內層迴圈 n 次
    // 總共 n × n = n^2 次運算
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            count += 1;
        }
    }

    cout << count << "\n";   // 迴圈跑完才輸出一次
    return 0;
}

估算：

• 如果 n = 10^4（萬），運算次數 = 10^8，約 0.1 秒 ✓
• 如果 n = 10^5（十萬），運算次數 = 10^{10}，約 10 秒 ✗ TLE 了！

這個估法算的是計算次數。如果迴圈裡還塞了大量 cout 輸出，實際會比估出來的慢得多——輸出為什麼特別慢，見本節後面「為什麼題目的輸入通常沒那麼大？」。

時間限制是 OJ 題目的核心條件之一。熟悉這個估計法，能幫你快速判斷解法是否可行，避免浪費時間寫一個注定 TLE 的程式。

¶為什麼題目的輸入通常沒那麼大？

你可能會想：既然 1 秒能做 10^9 次運算，題目為什麼很少真的給到 10^9 筆資料？

關鍵在輸入輸出（讀資料、印答案）特別慢。前面說的「簡單運算」是加、減、比較這種；但讀進一個數字要慢得多——程式得一個字元一個字元把它讀進來、再拼成一個數字，跟純計算比起來是好幾倍的功夫。所以就算題目真的塞給你 10^9 個數字，光是把它們讀進來就可能花上好幾秒，你還沒開始算就先 TLE 了。

這就是為什麼你會發現：大部分題目的輸入量離 10^9 很遠，n 通常落在 10^5 \sim 10^6。 看到題目把 n 開到這個大小，一方面是在提醒你「別用太慢的做法」，另一方面也代表你不用擔心 10^9 那種規模。

¶在 OJ 上實測平台速度

10^9 終究是別人告訴你的數字。每個 OJ 的機器快慢、編譯選項都不同——最可靠的作法是拿一段簡單的測速程式，到你做題的平台上實際跑一次：

#include<iostream>
using namespace std;
int main() {
    long long sum = 0;
    for (long long i = 1; i <= 1000000000; i++) {   // 10^9 圈
        sum += i % 3;   // 加一點小變化，讓編譯器乖乖一圈一圈跑
    }
    cout << sum << "\n";   // 結果一定要輸出
    return 0;
}

在 AACPOJ，把這段貼進任何題目頁的自訂測試執行（不需要輸入），看回報的執行時間；其他平台可以找一題能自由提交的題目交上去，看時間欄位。這段程式在 AACPOJ 的評測機上實測約 0.8 秒——「一秒約 10^9 次」在這個平台是準的；換一個平台，就重測一次。

¶反過來用：看輸入大小猜做法

熟悉估法後可以反過來用：看題目給的 n 有多大，反推程式最多能跑幾層迴圈——

• n 到 10^6 左右：大概只能把每筆資料看過一遍（一層迴圈，約 n 次）。
• n 只有幾千：可以用兩層迴圈（約 n \times n 次），再大就會太慢。
• n 只有一、二十：連「把每一種組合都試一遍」這種最暴力的做法都跑得動。

例如題目說 n 最大 10^5，那雙層迴圈（約 10^{10} 次）就太慢、會 TLE，得改想一個只跑一層、大約 n 次的做法。

這套「看輸入大小猜做法」的直覺，下冊 10.1 會配上競程通用的 O 記號，升級成一套三步驟的估時流程。

¶動手試試看

1. 估計 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) x++; 在 n = 10^5 時大約要跑多久，會不會 TLE？
2. 一題的 n 最大到 2 \times 10^5、時限 1 秒。你想用雙層迴圈解（每筆資料都跟其他每筆比一次，約 n^2 次）——先估估看行不行？如果不行，代表你得換一個少一層迴圈的做法。
3. 把「在 OJ 上實測平台速度」的測速程式丟進 AACPOJ 題目頁的自訂測試跑一次，記下時間；再把 sum += i % 3; 改成 sum += i; 跑一次——時間為什麼差這麼多？