算法分析--数学模型

Question

我正在为算法做一些自我研究，我不知道为什么ThreeSum.count()中的if语句精确地执行N(N-1)(N-2)/6时间？我知道N引用了第一个for循环，等等，但是6是从哪里来的呢？对不起，如果这是一个非常简单的问题。

public static int count(int[] a)
{ // Count triples that sum to 0.
    int N = a.length;
    int cnt = 0;

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

Answer 1

让我们把它从下往上盖。最内环对每个j重复自己的j次数。

因此，它实际上重复了自己的sum(j | j=0,...,i-1)

我们知道 sum(j | j=0,...,i-1) = i(i-1)/2 = [i^2-i]/2

i重复自己的n时间，所以我们得到：

sum(i^2-i| i=0,...,n-1)/2 = [sum(i^2) - sum(i)]/2 = [n^3/3 - n^2/2 +n/6 - n^2/2 +n/2]/2
= n^3/6 -n^2/2 +4n/12 = (n^3 - 3n^2 +2n)/6

但我们也知道

n(n-1)(n-2) =n^3-3n^2 +2n

QED

我们在这里使用的公式是：

1. sum(i) - 算术级数
2. 和(i^2)- 平方和
3. n(n-1)(n-2) - binom

Answer 2

求出它的一个好方法是:只要有3个嵌套循环，迭代数不超过n，多项式的次数就不大于3。让我们假设它看起来像A* x^3 +B* x^2 +C*x+ D。Onecan计算它在4个任意点上的值(假设N= 0，1，2，3)，并求解线性方程组以求它的系数。