嵌套循环到数学模型中以计算操作次数
我正在读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？ 它背后的逻辑是什么？
任何帮助将不胜感激！
如果你能理解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 。
您可以使用Sigma表示法，并了解如何提出您书中提到的公式：
据我们所知…
1 + 2 + 3 + 4 … + N => N（N-1）/ 2
同样，最里面的循环就像
1.n + 2（N-1）+3（N-2）+ … N.1 => N（N-1）（N-2）/ 6
这是对此的certificate 。
6来自3！ （三个因子来自三个循环）。
考虑最外面的循环，比如说，包含5个元素的数组。 对于等式的那一部分，你计算N = 5，但是你只能在值i = 0，i = 1或i = 2的情况下到达你的内环。 类似地，你用（N-1）表示下一个循环，但是你只能到达你的内部循环中的值j = 1，j = 2或j = 3而不是由（N-1）暗示的四个值）。
除以6（对于三个循环）将补偿在到达最内层循环之前数组中的值将耗尽的值。