初始化为非零时，如何计算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)) { }

这应该为每个操作打印一行，这样你就可以计数要测量的行数；时间"；。(好吧，这是伪代码，所以你必须采用你的语言来运行它：(