如何在没有三个嵌套循环的情况下编码三重和

Question

我正在尝试有效地实现一个公式，如：

sum(i=1,n) sum(j=i+1,n) sum(k=j+1,n) x(i)*x(j)*x(k)

做到这一点的直接方法是这样的：

sum = 0
for (int i=1; i<n; i++ )
    for( int j=i+1; j<n; j++ )
        for( int k=j+1; k<n; k++ )
            sum += x[i]*x[j]*x[k]

问题是这是O(n^3). 我想知道是否有某种方法可以重写它，以便我可以使用一些递归关系消除一层甚至两层迭代。我尝试了以下方法，但没有运气：

for (int i=n; i>0; i-- )
    int sumK = 0
    for( int j=n; j>i; j-- ) {
         sum += sumK
         sumK += x[i]*x[j]*x[j]
    }

它给出了与直接代码不同的答案，但它确实消除了一层迭代，所以我认为我在正确的轨道上（尽管出轨了）。有人可以帮忙吗？

Answer 1

你从正式写成的这个公式开始：

要进行的第一个观察是，由于 x_i 和 x_j 相对于 k 是常数，并且它们正在相乘，因此您可以将它们从求和中分解出来，从而得到：

使用相同的逻辑，您可以从另一个求和中提取 x_i：

现在，您可以看到您只需要从 i..n 为每个计算 x 中元素的总和i < n（可以使用后缀总和在 O(n) 时间内完成），确保乘以您要计算的元素开始，考虑与 x_j 的乘法。这说明了最右边的总和。现在，你可以做同样的事情，但对于你之前得到的总和，确保乘以你开始的元素的值（以解释乘以 x_i）。这占中间总和。然后，您可以将之前结果中从 1 到 n 的所有值相加，得出最终答案。这是生成的java代码（查看函数fastProduct）：

import java.util.Random;

public class Test {
    public static void printArr(long[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i ++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static long naiveProduct(long[] arr) {
        long sum = 0;
        for (int i = 0; i < arr.length; i ++) {
            for (int j = i + 1; j < arr.length; j ++) {
                for (int k = j + 1; k < arr.length; k ++) {
                    sum += arr[i] * arr[j] * arr[k];
                }
            }
        }
        return sum;
    }

    public static long fastProduct(long[] arr) {
        long[] sums = new long[arr.length];
        sums[arr.length - 2] = arr[arr.length - 1];
        // pre-calculate the summations of x_k
        for (int j = arr.length - 3; j >= 1; j --) {
            sums[j] = sums[j + 1] + arr[j + 1];
        }
        // multiply by x_j
        for (int j = 1; j <= arr.length - 2; j ++) {
            sums[j] *= arr[j];
        }
        long[] sumSums = new long[arr.length];
        sumSums[arr.length - 3] = sums[arr.length - 2];
        // pre-calculate the summations of x_j times the summation of x_k
        for (int i = arr.length - 4; i >= 0; i --) {
            sumSums[i] = sumSums[i + 1] + sums[i + 1];
        }
        // multiply by x_i
        for (int i = 0; i <= arr.length - 3; i ++) {
            sumSums[i] *= arr[i];
        }
        long total = 0;
        // sum up the final summation
        for (int i = 0; i < arr.length - 2; i ++) {
            total += sumSums[i];
        }
        return total;
    }

    public static void main(String[] args) {
        long[] test = new long[10];
        Random rand = new Random();
        for (int i = 0; i < test.length; i ++) {
            test[i] = rand.nextInt(9) + 1;
        }
        printArr(test);
        System.out.printf("%d %d", naiveProduct(test), fastProduct(test));
    }
}