如何降低计算子数组和矩阵Y[i][j]的Python程序的时间复杂度？

你当前采用的三重循环实现，整体时间复杂度为O(n³)：两层循环遍历所有(i,j)组合生成矩阵元素，内层循环对每个(i,j)单独累加X中i到j的元素，平均单次累加的长度为O(n)，在n规模较大时运行效率会非常差。
这个问题存在成熟的优化方案，可以将整体时间复杂度降到O(n²)——这也是生成n阶结果矩阵的理论最优下界，毕竟矩阵本身包含n²个元素，无法绕过逐元素写入的开销。

优化方案1：前缀和公式法 #

先构建长度为n+1的前缀和数组prefix，定义规则为：

• prefix[0] = 0
• 对下标k从1到n，prefix[k] = sum(X[0..k-1])

构建完成后，任意闭区间子数组X[i..j]的元素和可以直接通过一步公式计算，无需循环累加：
Y[i][j] = prefix[j+1] - prefix[i]

整个流程只需要O(n)时间构建前缀和，加上O(n²)时间遍历填充结果矩阵，总复杂度为O(n²)，计算过程无嵌套累加循环。
举个简单校验例子：假设X = [2,4,1,5]，构建的前缀和为[0,2,6,7,12]，计算Y[1][3]（即X[1]+X[2]+X[3] =4+1+5=10），代入公式得prefix[4] - prefix[1] =12 -2=10，计算结果完全匹配。

优化方案2：逐行递推填充（更省空间） #

可以完全跳过单独构建前缀和数组的步骤，利用已有结果的递推关系直接填充Y矩阵，进一步降低额外空间开销：

• 固定左边界i，先填充矩阵对角线位置：单个元素的子数组和即为元素本身，因此Y[i][i] = X[i]
• 对同一个i，右边界j从i+1遍历到数组末尾，利用递推关系直接计算：
  Y[i][j] = Y[i][j-1] + X[j]

这个逻辑的本质是：左边界固定时，右边界每向右移动一位，子数组和只需要在之前的结果基础上加上新纳入的元素，完全不需要从头累加。整个流程同样只需要两层循环完成，总时间复杂度O(n²)，且除了结果矩阵本身的存储空间，不需要额外申请辅助数组的空间。

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