#P2243. 时间复杂度2

时间复杂度2

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

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

代码使用 C++14,work() 已定义且会正常返回。整数类型足够大,没有溢出;循环均会正常结束。代码片段按给定常量独立执行。请选择基本操作次数和是否超时均正确的一项。

1. 单选题(10分)

阅读下列代码:

long long x=1000000000000000000LL;
while(x>0){work();x/=2;}

{{ select(1) }}

  • 基本操作共 30 次,不会超时。
  • 基本操作共 60 次,不会超时。
  • 基本操作共 61 次,不会超时。
  • 基本操作共 120 次,不会超时。

2. 单选题(10分)

阅读下列代码:

const long long n=1LL<<60;
for(long long x=1;x<=n;x*=2) work();

{{ select(2) }}

  • 基本操作共 61 次,不会超时。
  • 基本操作共 122 次,不会超时。
  • 基本操作共 30 次,不会超时。
  • 基本操作共 62 次,不会超时。

3. 单选题(10分)

阅读下列代码:

const int n=10000000;
for(int i=0;i<n;++i)
  for(long long x=1;x<n;x*=2) work();

{{ select(3) }}

  • 基本操作共 240,000,001 次,会超时。
  • 基本操作共 240,000,000 次,会超时。
  • 基本操作共 480,000,000 次,会超时。
  • 基本操作共 120,000,000 次,不会超时。

4. 单选题(10分)

阅读下列代码:

const int n=5000000;
for(int i=0;i<n;++i)
  for(long long x=1;x<n;x*=2) work();

{{ select(4) }}

  • 基本操作共 115,000,001 次,不会超时。
  • 基本操作共 230,000,000 次,会超时。
  • 基本操作共 115,000,000 次,不会超时。
  • 基本操作共 57,500,000 次,不会超时。

5. 单选题(10分)

阅读下列代码:

const int n=2000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j)
    for(int x=1;x<n;x*=2) work();

{{ select(5) }}

  • 基本操作共 88,000,000 次,不会超时。
  • 基本操作共 22,000,000 次,不会超时。
  • 基本操作共 44,000,001 次,不会超时。
  • 基本操作共 44,000,000 次,不会超时。

6. 单选题(10分)

阅读下列代码:

const int n=5000;
for(int i=0;i<n;++i)
  for(int j=0;j<n;++j)
    for(int x=1;x<n;x*=2) work();

{{ select(6) }}

  • 基本操作共 325,000,001 次,会超时。
  • 基本操作共 162,500,000 次,不会超时。
  • 基本操作共 325,000,000 次,会超时。
  • 基本操作共 650,000,000 次,会超时。

7. 单选题(10分)

阅读下列代码:

const int n=1<<20;
for(int len=1;len<n;len*=2)
  for(int i=0;i<n;i+=len) work();

{{ select(7) }}

  • 基本操作共 4,194,300 次,不会超时。
  • 基本操作共 2,097,151 次,不会超时。
  • 基本操作共 2,097,150 次,不会超时。
  • 基本操作共 1,048,575 次,不会超时。

8. 单选题(10分)

阅读下列代码:

const int n=1<<26;
for(int len=1;len<n;len*=2)
  for(int i=0;i<n;++i) work();

{{ select(8) }}

  • 基本操作共 1,744,830,465 次,会超时。
  • 基本操作共 3,489,660,928 次,会超时。
  • 基本操作共 1,744,830,464 次,会超时。
  • 基本操作共 872,415,232 次,会超时。

9. 单选题(10分)

阅读下列代码:

const int n=1<<27;
for(int len=1;len<=n;len*=2)
  for(int i=0;i<len;++i) work();

{{ select(9) }}

  • 基本操作共 536,870,910 次,会超时。
  • 基本操作共 268,435,455 次,会超时。
  • 基本操作共 268,435,456 次,会超时。
  • 基本操作共 134,217,727 次,不会超时。

10. 单选题(10分)

阅读下列代码:

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

{{ select(10) }}

  • 基本操作共 50,000,013 次,不会超时。
  • 基本操作共 100,000,027 次,不会超时。
  • 基本操作共 200,000,054 次,会超时。
  • 基本操作共 100,000,028 次,不会超时。