print()是否属于基本指令？下述伪代码的基本指令总数是否为3+2n

问题解答 #

你给出的伪代码如下：

algorithm double(n)
begin
  i = 1;            | 1 basic instruction (=)
  while i ≤ n do:   | 2 basic instruction (< and =) 
    i = i * 2;      | 2 basic instruction (= and *) which "means" 2*n because the loop(?)
  print(i);         | 1 basic instruction (print)?
end

1. print()是否属于基本指令？

是。在基础的指令计数规则中，单次执行、运行时间固定的原子操作都属于基本指令，单次IO调用（如这里的print）执行时间不随输入规模n变化，常规统计时会计为1条基本指令，你的判断是对的。

2. 你的统计结果是否正确？

不正确，核心错误是对循环次数的判断：

• 循环中i的取值是1、2、4、8...2^k，直到2^k >n时终止，循环执行次数是⌊log₂n⌋ +1次，远小于你假设的n次。
• 除此之外还有一处遗漏：while的条件判断会比循环体多执行1次（最后一次判断不满足条件时也会执行一次判断）。

如果按照你预设的单步计数规则（赋值计1、比较+跳转计2、乘法+赋值计2、print计1），正确的总指令数计算逻辑是：

• 初始化i=1：1条
• while条件判断：共(⌊log₂n⌋ +2)次执行，每次计2条，合计2*(⌊log₂n⌋ +2)条
• 循环体i = i*2：共⌊log₂n⌋ +1次执行，每次计2条，合计2*(⌊log₂n⌋ +1)条
• print(i)：1条
  总计：1 + 2*(⌊log₂n⌋ +2) + 2*(⌊log₂n⌋ +1) +1 = 4⌊log₂n⌋ +8 条。如果你不需要精确到下取整，简化后时间复杂度是O(log n)，和你之前算的O(n)完全不同。

内容的提问来源于stack exchange，提问作者user14551665