algorithm - 计算if语句执行次数

Question

此代码计算有多少整数三元组和为 0:完整代码为 here .

initialise an int array of length n
int cnt = 0 // cnt is the number of triples that sum to 0
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        for (int k = j+1; k < n; k++) {
            if (array[i]+array[j]+array[k] == 0) {
                cnt++;
            }
        }
    }
}

现在，从 Robert Sedgewick 的《算法》一书中，我读到:

• 将cnt初始化为0只执行一次。
• cnt++ 从 0 到找到三元组的次数执行。
• if 语句执行了 n(n-1)(n-2)/6 次。

我做了一些实验，所有这些都是正确的。但我完全不知道他们如何计算 if 语句执行的次数。我不确定，但我认为:

• n表示从i到n
• (n-1)表示从i+1到n
• (n-2)表示从j+1到n
• /6 我不知道这是干什么的。

谁能解释一下如何计算这个？

Answer 1

这是总和。

1. 每次到达时，内部循环执行 n-j-1 次
2. 每次到达中间循环都会执行 n-i-1 次
3. 外层循环执行了 n 次。

Sum all of these并且您会得到 cnt++ 被调用的总次数。

---

注意中间循环每次执行的次数不是n-1，而是n-i-1，其中i 是外循环的索引。中间循环也是如此。

/6 因素来自于在求和公式中考虑它。