如何在R中高效计算不同索引下的求和运算？

首先，你的原表达式应该是对所有互不相同的索引k、l、s、t，求和以下乘积项：

Tn <- sum( (X[k]-X[l]) * (X[s]-X[t]) * (Y[k]-Y[l]) * (Y[s]-Y[t]) )

（注：原代码括号位置有误，推测为上述形式）

你之前的无限制求和方法会涉及O(n⁴)的计算量，当n较大时速度极慢。下面通过代数化简，用统计量直接计算，时间复杂度降为O(n)：

步骤1：定义基础统计量 #

先计算X和Y的各类统计量：

n <- length(X)
if (n < 4) {
  Tn <- 0  # 不足4个元素时无有效索引组合
} else {
  Sx <- sum(X)
  Sy <- sum(Y)
  Sxy <- sum(X * Y)
  Sx2 <- sum(X^2)
  Sy2 <- sum(Y^2)
  Sx2y <- sum(X^2 * Y)
  Sxy2 <- sum(X * Y^2)
  Sx2y2 <- sum(X^2 * Y^2)
}

步骤2：计算中间变量 #

# 计算所有k≠l的(Xk-Xl)(Yk-Yl)之和
sum_kl <- 2 * (n * Sxy - Sx * Sy)

# 计算所有k≠l的[(Xk-Xl)(Yk-Yl)]²之和
sum_kl_sq <- 2 * n * Sx2y2 + 2 * Sx2 * Sy2 - 
  4 * Sx2y * Sy - 4 * Sxy2 * Sx + 4 * Sxy^2

# 计算每个k对应的sum_{l≠k}(Xk-Xl)(Yk-Yl)的平方和
sum_Dk_sq <- (n-1)^2 * Sx2y2 + Sy^2 * Sx2 + Sx^2 * Sy2 + 
  n * Sxy^2 - 2*(n-1)*Sy*Sx2y - 2*(n-1)*Sx*Sxy2 + 
  2*(n-1)*Sxy^2 - 2*Sx*Sy*Sxy

步骤3：代入公式计算Tn #

通过代数推导，四互不相同索引的求和结果可由以下公式得到：

Tn <- sum_kl^2 - 4 * (sum_Dk_sq - sum_kl_sq) - 2 * sum_kl_sq

原理说明 #

该方法通过将四重求和转化为基础统计量的运算，避免了遍历所有索引组合。核心思路是先计算无限制的二重求和平方，再减去包含重复索引的情况，最终得到仅包含四互不相同索引的求和结果。

内容的提问来源于stack exchange，提问作者Tao