三重嵌套循环的复杂性

Question

我有以下算法来查找所有三元组

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)
                { cnt++; }

我现在有了三重循环，我检查了所有三重循环。如何证明从 N 项中可以选择的不同三元组的数量正好是 N*(N-1)*(N-2)/6 ?

如果我们有两个循环

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
             ...

当i = 0我们进入第二个循环N-1次

i = 1 => N-2 次

...

i = N-1 => 1 次

i = N => 0 次

所以0 + 1 + 2 + 3 + ... + N-2 + N-1 = ((0 + N-1)/2)*N = N*N - N/2

但是如何用三元组做同样的证明呢？

Answer 1

一种方法是实现这样的三元组的数量等于C(n, 3):

              n!
C(n, 3) =  --------
           3!(n-3)!

        = (n-2)(n-1)n/6

另一个是计算你的循环做了什么：

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
         for (int k = j+1; k < N; k++)

您已经展示了从 0 到 n-1 的两个循环执行 n(n-1)/2 操作。

对于 i = 0，内部循环执行 (n-1)(n-2)/2 操作。

对于 i = 1，内部循环执行 (n-2)(n-3)/2 操作。

...

对于 i = N - 1，内部循环执行 0 操作。

我们有：

(n-1)(n-2)/2 + (n-2)(n-3)/2 + ... =

= sum(i = 1 to n) {(n - i)(n - i - 1)/2}
= 1/2 sum(i = 1 to n) {n^2 - ni - n - ni + i^2 + i}
= 1/2 sum(i = 1 to n) {n^2} - sum{ni} - 1/2 sum{n} + 1/2 sum{i^2} + 1/2 sum{i}
= 1/2 n^3 - n^2(n+1)/2 - 1/2 n^2 + n(n+1)(2n+1)/12 + n(n+1)/4

这简化为正确的公式，但它变得太丑陋无法继续。您可以检查它是否在 Wolfram.

Answer 2

好的，我会一步步来的。这更像是一道数学题。

使用示例数组进行可视化：

[1, 5, 7, 11, 6, 3, 2, 8, 5]

第一次 3rd 嵌套循环从 7 开始，正确吗？

和 2nd 位于 5，1st 循环位于 1.

3rd 嵌套循环是重要的。

它将循环 n-2 次。然后 2nd 循环递增。

此时 3rd 循环循环了 n-3 次。

我们不断添加这些直到我们得到。

[(n-2) + (n-3) + ... + 2 + 1 + 0]

然后 1st 循环递增，所以这次我们从 n-3 开始。

所以我们得到：

[(n-3) + ... + 2 + 1 + 0]

将它们加在一起我们得到：

[(n-2) + (n-3) + ... + 2 + 1 + 0] +
[(n-3) + ... + 2 + 1 + 0]         +
[(n-4) + ... + 2 + 1 + 0]         +
.
.                                     <- (n-2 times)
.
[2 + 1 + 0]                       +
[1 + 0]                           +
[0]

我们可以将其重写为：

(n-2)(1) + (n-3)(2) + (n-4)(3) + ... + (3)(n-4) + (2)(n-3) + (1)(n-2)

在数学符号中我们可以这样写：

一定要查看求和的加法特性。（回到大学数学！）

我们有

=

... 记住如何将和转换为多项式

=

复杂度为O(n^3)。

三重嵌套循环的复杂性

Complexity of triple-nested Loop

algorithm

performance

time-complexity