#P2245. 空间复杂度
空间复杂度
本题是空间限制判断,不是选择大 复杂度。共10道代码阅读单选题,每题10分。
统一内存模型
- 内存上限为 64 MiB, 字节。
- 程序已有固定开销 8 MiB,需要加到每题所列的额外内存上;主函数内的普通变量等均已包含在这8 MiB中。
int占4字节,long long占8字节,unsigned char占1字节。- 数组/容器中的全部元素均实际占用内存;
vector的容量恰好等于长度,不计容器对象、分配器和对齐开销。忽略编译器消除分配等优化。 - 总占用严格大于64 MiB才算爆空间,恰好等于时不算。忽略运行时间,只判断该内存模型下的峰值占用。
代码为 C++17 片段,已包含所需头文件;use()已定义。请选择峰值总内存和是否爆空间均正确的一项。
1. 单选题(25 分)
根据统一内存模型,判断下列代码的峰值内存:
std::vector<int> a(10000000);
use(a);
{{ select(1) }}
- 峰值总占用 48,388,608 字节,不会爆空间。
- 峰值总占用 49,437,184 字节,不会爆空间。
- 峰值总占用 40,000,000 字节,不会爆空间。
- 峰值总占用 48,388,609 字节,不会爆空间。
2. 单选题(25 分)
根据统一内存模型,判断下列代码的峰值内存:
std::vector<long long> a(8000000);
use(a);
{{ select(2) }}
- 峰值总占用 72,388,609 字节,会爆空间。
- 峰值总占用 72,388,608 字节,会爆空间。
- 峰值总占用 73,437,184 字节,会爆空间。
- 峰值总占用 64,000,000 字节,不会爆空间。
3. 单选题(25 分)
根据统一内存模型,判断下列代码的峰值内存:
const int n=4000;
std::vector<int> a(n*n);
use(a);
{{ select(3) }}
- 峰值总占用 72,388,609 字节,会爆空间。
- 峰值总占用 73,437,184 字节,会爆空间。
- 峰值总占用 72,388,608 字节,会爆空间。
- 峰值总占用 64,000,000 字节,不会爆空间。
4. 单选题(25 分)
根据统一内存模型,判断下列代码的峰值内存:
std::vector<int> a(3000*3000);
std::vector<int> b(2000*2000);
use(a);use(b);
{{ select(4) }}
- 峰值总占用 61,437,184 字节,不会爆空间。
- 峰值总占用 52,000,000 字节,不会爆空间。
- 峰值总占用 60,388,609 字节,不会爆空间。
- 峰值总占用 60,388,608 字节,不会爆空间。