嵌套循环到数学模型中以计算操作次数

Question

我正在阅读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？它背后的逻辑是什么？

任何帮助将不胜感激!

Answer 1

如果你能理解这N(N-1)(N-2)部分,这里有一个想法:

结合使用3个数字,i,j,k,无论3个属于该范围,0 <= i,j,k < N还有不同的3个(在代码中也要注意这一点,这就是公式的原因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

六!

这些方法中有多少可以出现在代码中？只有一个!(这在初始化中得到了注意j和k).

所以,总数N(N-1)(N-2)应该除以6.