三嵌套循环的复杂度 [英] Complexity of triple-nested Loop

问题描述

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

  for（int i = 0; i< N; i ++） （int j = i + 1; j 如果（int k = j + 1; k 如果（a [i] + a [j] + a [k] == 0）
 {cnt ++; } 
  

我现在有了三重循环，并检查了所有三重循环。如何显示可以从N个项目中选择的不同三元组的数目恰好是 N *（N-1）*（N-2）/ 6 ？

如果我们有两个循环

 为（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

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

解决方案

好，我将逐步进行此操作。

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

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

第一次第3 个嵌套循环从 7 开始，对吗？

和位于 5 的第二个，位于 1 的 1st 循环。

第3 个嵌套循环是重要的循环。

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

这时第3 循环循环了 n-3 次。

我们一直添加这些，直到得到为止。

  [（n-2 ）+（n-3）+ ... + 2 + 1 + 0] 
  

然后strong>第一个循环递增，所以这次我们从 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次）
。 
 [2 +1 + 0] + 
 [1 + 0] + 
 [0] 
  

我们可以将其重写为：

 （n-2）（1）+（n- 3）（2）+（n-4）（3）+ ... +（3）（n-4）+（2）（n-3）+（1）（n-2）
  

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

< a href = https://i.stack.imgur.com/Jf5IQ.png rel = noreferrer>

请确保您查找求和的加和属性。 （返回大学数学！）

我们有

=

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

=

其复杂度为 O（n ^ 3）。

I have the following algorithm to find all triples

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++; }

I now that I have triple loop and I check all triples. How to show that the number of different triples that can be chosen from N items is precisely N*(N-1)*(N-2)/6 ?

If we have two loops

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

when i = 0 we go to the second loop N-1 times

i = 1 => N-2 times

...

i = N-1 => 1 time

i = N => 0 time

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

But how to do the same proof with triples?

解决方案

Ok, I'll do this step by step. It's more of a maths problem than anything.

Use a sample array for visualisation:

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

The first time the 3rd nested loop begins at 7, correct?

And the 2nd at 5, and the 1st loop at 1.

The 3rd nested loop is the important one.

It will loop through n-2 times. Then the 2nd loop increments.

At this point the 3rd loop loops through n-3 times.

We keep adding these till we get.

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

Then the 1st loop increments, so we begin at n-3 this time.

So we get:

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

Adding them all together we get:

[(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]

We can rewrite this as:

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

Which in maths notation we can write like this:

Make sure you look up the additive properties of Summations. (Back to college maths!)

We have

=

... Remember how to convert sums to polynomials

=

=

Which has a complexity of O(n^3).

这篇关于三嵌套循环的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！