algorithm - 一个简单循环中有多少个原始操作？

Question

我有一堆代码可以找到原始操作。问题是网络上并没有很多关于这个主题的详细资源。在这个循环中：

for i:=0 to n do
  print test
end

我们真的有多少步骤？在我的第一个猜测中，我会说 n+1 考虑 n 用于时间循环和 1 用于打印。然后我想，也许我不够精确。在每个循环中甚至没有将 1 添加到 i 的操作吗？就此而言，我们有 n+n+1=2n+1。那是对的吗？

score 4 · Accepted Answer

通过将循环重新转换为，可以将循环分解为其“原始操作” while：

int i = 0;
while (i < n)
{
    print test;
    i = i + 1;
}

或者，更明确地说：

loop:
    if (i < n) goto done
    print test
    i = i + 1
    goto loop
done:

然后您可以看到，对于每次迭代，都有一个比较、一个增量和一个goto. 这只是循环开销。您必须添加到循环中完成的任何工作。如果print被认为是“原始操作”，那么您有：

现在，如何将所有内容转换为机器代码高度依赖于编译器、运行时库、操作系统和目标硬件。也许还有其他事情。

1 回答 1