教材 / AA 競程語法書 上冊 / 第四單元 / 你的程式會不會太慢?(TLE)

4.9 你的程式會不會太慢?(TLE)

競程的題目都有時間限制(本單元的練習題是 0.25~1 秒)。如果程式跑得太慢、超過時限,會得到 TLE(Time Limit Exceeded,超出時間限制)。所以在動手寫之前,最好先大概估一下:這個做法會不會太慢?

基本法則:迴圈的每一圈只做幾件加減、比較這類簡單的事時,1 秒大約能跑 10^9 圈。

如何估計:

  1. 數一數最內層的迴圈大約會跑幾圈
  2. 除以 10^9,估出秒數的量級
  3. 估出來比時限小很多(例如不到十分之一)→ 放心寫;跟時限同一個量級 → 當作危險——換方法,或先實測確認

登入後即可閱讀完整內容

語法書免費開放給所有 AACPOJ 帳號,註冊只要一分鐘。