algorithm - 3 总和的时间复杂度

Question

我在下面提供了解决 3 和问题的代码片段。

       int N = 10; 

  for (int i = 0; i < N; i++)// this line gets executed N times
    for (int j = i+1; j < N; j++)// this line gets executed N(N-1) times
      for (int k = j+1; k < N; k++)// this line gets executed  N(N-1)(N-2) times
         if (a[i] + a[j] + a[k] == 0)// How many times does this line gets executed
             cnt++;

我用的课本上说的是那行

if (a[i] + a[j] + a[k] == 0)

被执行 (N(N-1)(N-2))/6 次。但根据我的分析，该语句被执行 (N(N-1)(N-2))

为什么要除以6，有什么证明。

Answer 1

你的代码实际上是在做一道排列组合题:从n个元素中取出三个不同的元素，看它们的和是否为零。那么从n个元素中提取出多少种三种不同元素的组合呢？数学告诉你 (N,3)=N*(N-1)(N-2)/3!=N(N-1)*(N-2)/6