E. 時間 vs 記憶體估計速查表
¶E-1. 時間複雜度估計表
| N 的範圍 | O(1) | O(log N) | O(N) | O(N log N) | O(N²) | O(N³) | O(2^N) |
|---|---|---|---|---|---|---|---|
| 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| 10² (100) | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ |
| 10³ (1,000) | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ |
| 10⁴ (10,000) | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ |
| 10⁵ (100,000) | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ |
| 10⁶ (1,000,000) | ✓ | ✓ | ✓ | △ | ✗ | ✗ | ✗ |
| 10⁷ (10,000,000) | ✓ | ✓ | △ | ✗ | ✗ | ✗ | ✗ |
| 10⁸ (100,000,000) | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ |
| 10⁹ (1,000,000,000) | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
說明：
- ✓ = 一般情況下能在 1 秒內完成
- △ = 臨界（邊界情況，通常需要 I/O 優化）
- ✗ = 會超時 (TLE)
時間限制通常為 1～2 秒；現代 CPU 約可執行 10^8～10^9 次簡單操作。
¶E-2. 記憶體複雜度估計表
| 陣列大小 | int 型 (4 bytes) | long long 型 (8 bytes) | 備註 |
|---|---|---|---|
| 10⁴ | 40 KB | 80 KB | 幾乎無壓力 |
| 10⁵ | 400 KB | 800 KB | 無壓力 |
| 10⁶ | 4 MB | 8 MB | 無壓力 |
| 2 × 10⁶ | 8 MB | 16 MB | 無壓力 |
| 10⁷ | 40 MB | 80 MB | 接近限制 |
| 2 × 10⁷ | 80 MB | 160 MB | 超過 128 MB 限制，風險 |
記憶體限制通常為 256 MB 或 128 MB；全域陣列比函式內陣列安全（且不會因遞迴而爆棧）。
¶E-3. 常見演算法的時間複雜度
| 演算法 | 時間複雜度 | 適用範圍 |
|---|---|---|
| 遍歷陣列 | O(N) | 任何 N |
| 排序（sort） | O(N log N) | N ≤ 10^6 (通常) |
| 二分搜 | O(log N) | 任何 N |
| 線性搜尋 | O(N) | 任何 N |
| 巢狀迴圈遍歷 | O(N²) | N ≤ 10^4 |
| DFS / BFS | O(V + E) | 圖論，V ≤ 10^5 |
| 動態規劃 | 視狀態數決定 | 狀態 ≤ 10^6 |