#P2242. 时间复杂度1

时间复杂度1

这是代码阅读单选题,每小题10分,共100分。

采用本题专用的理想模型:1 秒最多执行 2×1082\times10^8 次基本操作。只将一次 work() 调用计为一次基本操作;循环控制、比较、赋值、函数调用和其他语句的开销均忽略。基本操作次数超过 2×1082\times10^8 才判为超时,恰好等于时不超时。这是学习用模型,不代表实际评测机耗时。

整数类型足够大,没有溢出;循环均会正常结束。代码片段按给定常量独立执行。请选择基本操作次数和是否超时均正确的一项。

1. 单选题(10分)

阅读下列代码:

const long long n = 100000000;
for (long long i=0; i<n; ++i) work();

{{ select(1) }}

  • 基本操作共 50,000,000 次,不会超时。
  • 基本操作共 100,000,000 次,不会超时。
  • 基本操作共 100,000,001 次,不会超时。
  • 基本操作共 200,000,000 次,不会超时。

2. 单选题(10分)

阅读下列代码:

const long long n = 300000000;
for (long long i=0; i<n; ++i) work();

{{ select(2) }}

  • 基本操作共 300,000,000 次,会超时。
  • 基本操作共 600,000,000 次,会超时。
  • 基本操作共 150,000,000 次,不会超时。
  • 基本操作共 300,000,001 次,会超时。

3. 单选题(10分)

阅读下列代码:

const int n=10000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j) work();

{{ select(3) }}

  • 基本操作共 100,000,001 次,不会超时。
  • 基本操作共 100,000,000 次,不会超时。
  • 基本操作共 200,000,000 次,不会超时。
  • 基本操作共 50,000,000 次,不会超时。

4. 单选题(10分)

阅读下列代码:

const int n=20000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j) work();

{{ select(4) }}

  • 基本操作共 400,000,001 次,会超时。
  • 基本操作共 800,000,000 次,会超时。
  • 基本操作共 400,000,000 次,会超时。
  • 基本操作共 200,000,000 次,不会超时。

5. 单选题(10分)

阅读下列代码:

const int n=20000;
for(int i=0;i<n;++i)
  for(int j=0;j<i;++j) work();

{{ select(5) }}

  • 基本操作共 399,980,000 次,会超时。
  • 基本操作共 99,995,000 次,不会超时。
  • 基本操作共 199,990,001 次,不会超时。
  • 基本操作共 199,990,000 次,不会超时。

6. 单选题(10分)

阅读下列代码:

const int n=20001;
for(int i=0;i<n;++i)
  for(int j=0;j<i;++j) work();

{{ select(6) }}

  • 基本操作共 200,010,001 次,会超时。
  • 基本操作共 100,005,000 次,不会超时。
  • 基本操作共 200,010,000 次,会超时。
  • 基本操作共 400,020,000 次,会超时。

7. 单选题(10分)

阅读下列代码:

const int n=50000000;
for(int round=0;round<4;++round)
  for(int i=0;i<n;++i) work();

{{ select(7) }}

  • 基本操作共 400,000,000 次,会超时。
  • 基本操作共 200,000,001 次,会超时。
  • 基本操作共 200,000,000 次,不会超时。
  • 基本操作共 100,000,000 次,不会超时。

8. 单选题(10分)

阅读下列代码:

const int n=30000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;j+=2) work();

{{ select(8) }}

  • 基本操作共 450,000,001 次,会超时。
  • 基本操作共 900,000,000 次,会超时。
  • 基本操作共 450,000,000 次,会超时。
  • 基本操作共 225,000,000 次,会超时。

9. 单选题(10分)

阅读下列代码:

const int n=15000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j) work();
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j) work();

{{ select(9) }}

  • 基本操作共 900,000,000 次,会超时。
  • 基本操作共 450,000,000 次,会超时。
  • 基本操作共 450,000,001 次,会超时。
  • 基本操作共 225,000,000 次,会超时。

10. 单选题(10分)

阅读下列代码:

const int n=100000000;
for(int i=0;i<n;i+=2) work();
for(int i=0;i<n;++i) work();

{{ select(10) }}

  • 基本操作共 75,000,000 次,不会超时。
  • 基本操作共 150,000,000 次,不会超时。
  • 基本操作共 300,000,000 次,会超时。
  • 基本操作共 150,000,001 次,不会超时。