#P2245. 空间复杂度

空间复杂度

本题是空间限制判断,不是选择大 OO 复杂度。共10道代码阅读单选题,每题10分。

统一内存模型

  • 内存上限为 64 MiB,1 MiB=1024×10241\text{ MiB}=1024\times1024 字节。
  • 程序已有固定开销 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 字节,不会爆空间。