嵌套循环进入数学模型以计算操作数

小编典典

嵌套循环进入数学模型以计算操作数

algorithm

我正在阅读Sedgewick和Wayne的《算法-第四版》一书，我必须承认“算法分析”一章的某些部分使我感到困惑！这可能是由于我缺乏数学知识引起的。

书中的某个地方有一个程序示例，其中的内循环被说成恰好执行了N（N-1）（N-2）/ 6次。这里是：

    public static int count(int[] a) {
        int count = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; i < a.length; j++) {
                for (int k = j + 1; k < a.length; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        count++; 
                    } 
                }
            }
        }
        return count;
    }

我熟悉大的O表示法，但是当要计算循环中确切的运算次数时，我迷路了。我了解N（N-1）（N-2）部分，但是为什么我们必须除以6？它背后的逻辑是什么？

任何帮助将不胜感激！

阅读 242

2020-07-28

共1个答案

小编典典

如果您能理解该N(N-1)(N-2)部分，则有以下想法：

取3个数字的组合，即i，j，k，无论这3个数字属于哪个范围，0 <= i,j,k < N并且彼此不同（这在代码中也要小心，这就是为什么公式N(N-1)(N-2)不是的原因N^3。

现在，让我们说数字是13、17、42。它们的轮回数字并不重要。您可以采用几种方式排列它们？

13-17-42
13-42-17
17-13-42
17-42-13
42-13-17
42-17-13

六！

这些方式中有多少种可以出现在代码中？只有一个！（这是照顾中的initializaton j和k）。

因此，的总数N(N-1)(N-2)应除以6。

2020-07-28