6.6 記憶體用量估計與 MLE
陣列會消耗記憶體。如果開的陣列太大，程式會因為記憶體不足被 OJ 判為 MLE（Memory Limit Exceed）。學會估算記憶體用量，是避免 MLE 的關鍵。
基本公式：
陣列記憶體用量 = 元素個數 × 單個元素的大小常見資料型態的大小：
| 資料型態 | 位元數 | 位元組 |
|---|---|---|
bool |
1 bit | 1 B |
char |
8 bits | 1 B |
short |
16 bits | 2 B |
int |
32 bits | 4 B |
long long |
64 bits | 8 B |
double |
64 bits | 8 B |
單位換算：
1 KB = 2^10 Bytes ≈ 1000 B
1 MB = 2^20 Bytes ≈ 1,000,000 B
1 GB = 2^30 Bytes ≈ 1,000,000,000 B¶範例程式碼
#include<iostream>
using namespace std;
int main() {
// 假設題目記憶體限制是 256 MB
const int MEMORY_LIMIT_MB = 256;
const long long MEMORY_LIMIT_BYTES = MEMORY_LIMIT_MB * (1LL << 20);
// 情境 1：開一個 int 陣列
// int 佔 4 bytes，問能開多大？
cout << "Max int elements: " << MEMORY_LIMIT_BYTES / 4 << '\n';
// 情境 2：開一個 long long 陣列
// long long 佔 8 bytes
cout << "Max long long elements: " << MEMORY_LIMIT_BYTES / 8 << '\n';
// 情境 3：開一個 2D 陣列 int[1000][1000]
long long elements_2d = 1000LL * 1000 * sizeof(int);
cout << "2D int[1000][1000] memory (MB): " << elements_2d / (1LL << 20) << '\n';
return 0;
}
執行結果：
Max int elements: 67108864
Max long long elements: 33554432
2D int[1000][1000] memory (MB): 3¶資源估計對照表
為了加強你對時間和記憶體的直覺，這裡列出常見的估計數據：
| 操作 | 時間複雜度 | 常用上限 | 備註 |
|---|---|---|---|
| 單個運算 | O(1) | N ≤ 10¹⁸ | 加減乘除等 |
| 線性遍歷 | O(N) | N ≤ 10⁸ | 一層迴圈 |
| 巢狀迴圈 | O(N²) | N ≤ 10⁴ | 兩層迴圈 |
| 三層迴圈 | O(N³) | N ≤ 500 | 三層迴圈 |
| 資料結構 | 記憶體 | 常用上限 | 備註 |
|---|---|---|---|
int 陣列 |
4 B/元素 | 6.4 × 10⁷ | 256 MB 限制 |
long long 陣列 |
8 B/元素 | 3.2 × 10⁷ | 256 MB 限制 |
int[1000][1000] |
4 MB | ✓ 可行 | 普通地圖 |
int[10000][10000] |
400 MB | ✗ 超限 | 超過 256 MB |
動手試試看：計算以下情境的記憶體用量：
- 一個
int a[10000000]的陣列 - 一個
int grid[5000][5000]的 2D 陣列 - 一個
long long cube[100][100][100]的 3D 陣列
執行上面的程式碼，看看你的計算是否正確。