求和意义和性质

当一个算法包含循环结构, 例如 while 或 for, 我们常常可以把它的运行时间表示为每次迭代所花时间之和. 因此, 求和不仅是数学中的基础工具, 也是算法分析中最常见的表达形式之一.

求和符号

在数学中, 求和符号写作 $$\sum$$ 读作 sigma(西格玛). 它表示一系列数值的累加.¹

一个典型写法是: $$\sum _{i=1}^n{a}_i$$

其中:

• $i=1$ 是起始下标, 表示从第 $1$ 项开始求和;
• $n$ 是终止下标, 表示求到第 $n$ 项;
• $a_i$ 是被累加的项.

等价地, $$\sum _{i=1}^n{a}_i=a_1+a_2+\cdots +a_n$$

如果把上限扩展到无穷大, 就得到无穷级数:² $$\sum _{i=1}^{\infty }{a}_i=a_1+a_2+a_3+\cdots$$

线性性质

求和最重要的性质之一是线性.

对于任意数列 $a_k$、$b_k$, 有: $$\sum _{k=1}^n(a_k+b_k)=\sum _{k=1}^n{a}_k+\sum _{k=1}^n{b}_k$$

对于常数 $c$, 有: $$\sum _{k=1}^{n}c{a}_k=c\sum _{k=1}^n{a}_k$$

合并起来, 可写成: $$\sum _{k=1}^n(c{a}_k+b_k)=c\sum _{k=1}^n{a}_k+\sum _{k=1}^n{b}_k$$

这一性质非常适合用于拆分复杂求和式, 例如: $$\sum _{i=1}^n(3i^2+2i+1)=3\sum _{i=1}^n{i}^2+2\sum _{i=1}^{n}i+\sum _{i=1}^{n}1$$

常见求和公式

等差和

最经典的求和是自然数和: $$\sum _{i=1}^{n}i=1+2+\cdots +n$$

用高斯配对法可得: $$\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$$

其增长阶为: $$\sum _{i=1}^{n}i=\Theta (n^2)$$

平方和

平方和公式为: $$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$

其增长阶为: $$\sum _{i=1}^n{i}^2=\Theta (n^3)$$

立方和

立方和公式为: $$\sum _{i=1}^n{i}^3={\left(\frac{n(n+1)}{2}\right)}^2$$

其增长阶为: $$\sum _{i=1}^n{i}^3=\Theta (n^4)$$

几何级数

几何级数在算法分析中也极其常见: $$\sum _{i=0}^{n-1}a{r}^i=a+ar+a{r}^2+\cdots +a{r}^{n-1}$$

当 $r\ne 1$ 时, 有: $$\sum _{i=0}^{n-1}a{r}^i=a\frac{1-r^n}{1-r}$$

如果 $|r|<1$ 且 $n\to \infty$, 则无穷几何级数收敛: $$\sum _{i=0}^{\infty }a{r}^i=\frac{a}{1-r}$$

望远镜求和

有些求和式可以通过相邻项抵消, 形成“望远镜”效果.

例如: $$\sum _{i=1}^n((i+1{)}^2-i^2)$$

展开后大部分项会抵消, 最后只剩首尾项: $$\sum _{i=1}^n((i+1{)}^2-i^2)=(n+1{)}^2-1$$

这类技巧常用于推导闭式公式, 也常用于证明一些求和恒等式.

与算法分析的关系

很多算法的运行时间都能写成求和形式. 例如:

• 线性扫描: $$T(n)=\sum _{i=1}^{n}c=\Theta (n)$$

• 双重循环: $$T(n)=\sum _{i=1}^n\sum _{j=1}^{n}c=\Theta (n^2)$$

• 嵌套循环但内层次数逐渐变化: $$T(n)=\sum _{i=1}^{n}i=\Theta (n^2)$$

• 分治递归展开后常得到几何级数或混合级数.

因此, 掌握求和不仅是为了做数学题, 更是为了把算法时间复杂度算出来.

编程中的求和

Rust 中可以直接利用迭代器来实现求和.

通用求和

pub fn sigma_sum<T, F>(start: i32, end: i32, f: F) -> T
where
    T: std::iter::Sum,
    F: Fn(i32) -> T,
{
    (start..=end).map(f).sum()
}

// 例: 计算 1^2 + 2^2 + ... + 5^2
let ans: i32 = sigma_sum(1, 5, |x| x * x);

等差和的 O(1) 公式

对于 1 + 2 + ... + n 这类等差和, 可以直接使用公式而不是循环累加:

pub fn gauss_sum(start: i64, end: i64) -> i64 {
    let len = end - start + 1;
    let sum = start + end;

    if len % 2 == 0 {
        (len / 2) * sum
    } else {
        len * (sum / 2)
    }
}

这样做把时间复杂度从 \Theta(n) 降到了 \Theta(1).

1. 若级数极限存在, 则称其收敛; 否则称其发散. ↩

2. 对于收敛级数, 求和顺序并不总能随意交换; 若级数绝对收敛, 则可交换求和顺序. ↩