的code倍嵌套被处决的for循环中的Java [英] Times of code been executed in a nested for loop in Java

问题描述

我最近读的书叫的算法的罗伯特·塞奇威克。我碰到一块code，而读算法分析。在code是如下：

I am recently reading the book called Algorithms by Robert Sedgewick. I came across one piece of code while reading "Analysis of Algorithms". The code is as follow :

public static int count(int a[]) {
    int N = a.length;
    int cnt = 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 (a[i] + a[j] + a[k] == 0) {  //here 
                    cnt++;
                }
            }
        }
    } 
    return cnt
}

我想知道是多少次如果语句来在为 -loop被处决。通过这本书提供的答案是 N（N-1）（N-2）/ 6 。但我不知道为什么，任何人都可以解释。

What I want to know is how many times of the if-statement within the for-loop been executed. The answer provided by the book is N(N-1)(N-2)/6. But I don't know why, could anyone explain.

推荐答案

您只需要评估以下款项：

You just need to evaluate the following sum:

您可以这样做手工，但<一个href="http://www.wolframalpha.com/input/?i=Sum%5BSum%5BSum%5B1,%20%7Bk,%20j%2b1,%20N-1%7D%5D,%20%7Bj,%20i%2b1,%20N-1%7D%5D,%20%7Bi,%200,%20N-1%7D%5D"相对=nofollow> Wolfram Alpha的是在那个好多了。

You could do that by hand, but Wolfram Alpha is much better at that.

不难验证

(N-1)(N-2) = N2 - 3N + 2

这表明你给的公式。

which shows the formula you gave.

对于人工分析：

开始与内总和，这是很容易：

Start with the inner sum, which is easy:

在中间的总和堵这给：

该款项会更容易评估，如果虚拟变量，从0开始（而不是 I + 1 ），因此我们应用虚拟改造 P =的J - 我 - 1 ：

This sum would be easier to evaluate if the dummy variable started from 0 (rather than i+1), therefore we apply the dummy transformation p = j - i - 1:

最后，必须插入外之和：

Finally, this must be plugged in the outer sum:

这篇关于的code倍嵌套被处决的for循环中的Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！