初始化非零时如何计算for循环的原始比较操作？

Question

for循环如下：

for(i = 0; i < n; i++){

}

初始化算1次操作，条件测试执行n+1次，递增n次。这给出了 T(n) = 1 + n + 1 + n = 2n + 2。我明白这一点。我感到困惑的地方是我被分配了一个非零值。我假设当 i = 1 时比较只发生 n 次并导致 T(n) = 1 + n + n = 2n + 1？但是如果我被分配到 10 会发生什么？还是负值？比较次数还是n还是n+1？

Answer 1

让我们用 i0 的初始化替换 0 的初始化，使整个事情更通用。

所以伪代码如下所示：

i0 = 0;
for (i = i0; i < n;  i++) { }

现在我们可以更一般地表述公式：

T(n) = T_init(n) + T_cmp(n) + T_inc(n)
     = 1         + (n-i0+1) + (n - i0)
     = 2*(n - i0 + 1)
     = 2*n - 2*i0 + 2

T_init应该清楚了。正如你所说，初始化总是运行只有一次，与 n.

无关

比较始终运行直接在增量之后，但也在第一次循环迭代之前进行一次。所以 T_cmp(n) = T_inc(n) + 1.

您也可以尝试使用一些辅助函数：

function init() {
  print("init");
  return i0;
}
function cmp(i,n) {
  print("cmp");
  return i < n;
}
function inc(i) {
  print("inc");
  return i+1;
}
for (i = init(); cmp(i,n); i = inc(i)) { }

这应该为每个操作打印一行，这样您就可以计算行数来测量“时间”。（好吧，这是伪代码，所以你必须适应你的语言才能运行 :)

初始化非零时如何计算for循环的原始比较操作？

How to count primitive comparison operations of for loop when initialization is non-zero?

big-o

complexity-theory