algorithm - 如何正式地解释一些操作？

Question

给定以下代码:

Function Fun(int n) {
    int j, k, t=1;
    for (j=0; j<=4*n^2; j+=4) {
        for (k=j; k<=4*sqrt(n); k+=4) {
            t+=8;
        }
    }
}

我想统计命令t+=8;被执行了多少次。

我发现，通过尝试 n 的几个值，它被执行了:

次。但是，我该如何正式解释呢？

Answer 1

这部分:

for (j=0; j<=4*n^2; j+=4){
    for (k=j; k<=4*sqrt(n); k+=4){
        t+=8;
    }
}

足以回答您的问题。

注意它类似于:

for (j=0; j<=n^2; j++){
    for (k=4*j; k<=4*sqrt(n); k+=4){
        t+=8;
    }
}

类似于:

for (j=0; j<=n^2; j++){
    for (k=j; k<=sqrt(n); k++){
        t+=8;
    }
}

1) 第一个for表示第二个执行了多少次

2) 第二个for表示t+=8;执行了多少次

让我们解释一下您的公式的两个部分:

• 第二部分与您的第二个for相关: k 为步骤 j 取 Math.floor(Math.sqrt(n)) - j + 1 值(当 j=0 => Math.floor(Math.sqrt(n)) + 1 值)
• 第一部分与您的第一个for 相关。但是为什么你有 sqrt(n) 而不是 n^2 ？这是棘手的部分。如果分析第二个循环何时生效，您会发现任何大于 sqrt(n) 的 j 都是无用的(第二个“for content”未执行因为 k 的上限是 sqrt(n) )。这就是为什么在公式中有 sqrt(n)。

发生这种情况是因为您的代码实际上类似于:

for (j=0; j<=sqrt(n); j++){
    for (k=j; k<=sqrt(n); k++){
        t+=8;
    }
}