4

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

任何帮助将不胜感激！

4

4 回答 4

7

如果你能理解这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

六！

这些方式中有多少可以出现在代码中？只有一个！j（这在和的初始化中得到了注意k）。

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

于 2012-08-11T14:37:29.557 回答
4

您可以使用 Sigma 符号并了解如何得出书中提到的公式：

在此处输入图像描述

于 2014-06-06T16:10:11.917 回答
1

据我们所知...

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

这是一个证明。

于 2012-08-11T14:37:52.647 回答
1

6 是从 3 派生的！（三个阶乘衍生自三个循环）。

考虑最外层的循环，比如说，一个包含 5 个元素的数组。您为等式的这一部分计算 N=5，但您只会到达值 i=0、i=1 或 i=2 的内部循环。同样，您用 (N-1) 表示下一个循环，但您只会到达值 j=1、j=2 或 j=3 的内部循环，而不是 (N-1) 隐含的四个值）。

除以 6（对于三个循环）可以补偿在到达最内层循环之前数组中的值用完的值。

于 2012-08-11T15:23:01.070 回答