Python代码优化请求：优化计算2*j+i+1求和的双重循环代码

你的原代码采用双重循环（外层遍历j，内层通过生成器计算i的累加），时间复杂度为O(n²)，当n较大时性能会急剧下降。我们可以通过数学推导将累加和转化为直接计算的公式，把时间复杂度降到O(1)。

数学推导过程 #

我们需要计算的总和是：
$$\sum_{j=0}^n \sum_{i=j}^n (2j + i + 1)$$
将其拆分为三个独立的求和项分别计算：

1. 常数项求和：$\sum_{j=0}^n \sum_{i=j}^n 1$
   对每个j，i的取值有$(n-j+1)$个，因此总和为$\sum_{k=1}^{n+1}k = \frac{(n+1)(n+2)}{2}$（令$k=n-j+1$）。

2. i项求和：$\sum_{j=0}^n \sum_{i=j}^n i$
   内层对i的求和为$\frac{(j+n)(n-j+1)}{2}$，对j从0到n求和后化简可得$\frac{n(n+1)(n+2)}{3}$。

3. 2j项求和：$\sum_{j=0}^n \sum_{i=j}^n 2j$
   内层每个j被累加$(n-j+1)$次，求和后化简可得$\frac{n(n+1)(n+2)}{3}$。

将三个项合并后，最终的求和公式为：
$$\text{总和} = \frac{(n+1)(n+2)(4n+3)}{6}$$

优化后的代码 #

直接代入公式计算，无需任何循环：

def get_sum(n):
    return (n + 1) * (n + 2) * (4 * n + 3) // 6

验证正确性 #

• 当n=0时，原代码返回1，公式计算结果为$\frac{1×2×3}{6}=1$，一致。
• 当n=1时，原代码返回7，公式计算结果为$\frac{2×3×7}{6}=7$，一致。
• 当n=2时，原代码返回22，公式计算结果为$\frac{3×4×11}{6}=22$，一致。

效率对比 #

• 原代码：n=10000时，需要执行约5000万次运算，耗时数秒甚至更久。
• 优化后代码：无论n多大，仅需几次算术运算，耗时可忽略不计。

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