求和意义和性质

当一个算法包含循环控制结构时, 例如while或者for循环, 我们可以将算法的运行时间表示为每一次执行循环体所花时间之和. 通过累加每次迭代所用时间, 可以获得其和(或称级数).

符号

在数学上, 我们有一个求和符号——∑(英语名称: sigma, 汉语名称: 西格玛, 是第十八个希腊字母).

作用: 表示一系列数值的累加.

基本用法: $$\sum _{i=1}^{n}i$$

• 下标( $i=1$ ): 起始序号, 表示求和变量的起始值
• 上标( $n$ ): 终止序号, 表示求和变量的终止值.
• 待求和的项( $i$ )

例: 给定一个数列 $a_1,a_2,\dots ,a_n$,其中$n$是非负整数, 可以将有限和 $a_1+a_2+\cdots +a_n$ 写作: $$\sum _{i=1}^n{a}_i$$ 并且: $$\sum _{i=1}^n{a}_i=a_1+a_2+\cdots +a_n$$ 让该数列无限延长( $a_1,a_2,\dots$ ), 则有: $$\sum _{i=1}^{\infty }{a}_i=a_1+a_2+\dots$$ 即: $$\underset{i\to \infty }{\lim }\sum _{i=1}^{\infty }$$

当其极限不存在时, 该级数¹发散；反之, 该级数收敛. 对于收敛级数, 不能随意对其项改变求和顺序. 而对于绝对收敛级数(若对于级数${\sum }_{i=1}^{\infty }{a}_i$有级数${\sum }_{i=1}^{\infty }|a_i|$也收敛, 则称其为绝对收敛级数), 则可以改变其项的求和顺序.

性质

线性性质

对于求和, 我们有下面的两个基本线性性质: $$\sum _{k=1}^n(a_k+b_k)=\sum _{k=1}^n{a}_k+\sum _{k=1}^n{b}_k$$ $$\sum _{k=1}^{n}c\cdot a_k=c\cdot \sum _{k=1}^n{a}_k(c\text{ 为常数})$$ 将两个综合起来就有: 对于任意实数$c$和任意有限序列$a_1,a_2,\dots ,a_n$和$b_1,b_2,\dots ,b_n$, 有 $$\sum _{k=1}^n(c\cdot a_k+b_k)=c\cdot \sum _{k=1}^n{a}_k+\sum _{k=1}^n{b}_k$$ 注: 线性性质对于无限收敛级数同样适用. 线性性质可以用来对项中包含渐近记号的和式求和.

等差级数

等差数列的前$n$项和称为一个等差级数², 也叫算术级数. 常见的有: $$\sum _{k=1}^{n}k=1+2+3+\cdots +n$$ 用高斯求和, 得 $$\begin{array}{rl}\sum _{k=1}^{n}k& =1+2+3+\cdots +n\\ & =\frac{n(n+1)}{2}\\ & =\Theta (n^2)\end{array}$$

平方和、立方和的求和公式

平方和公式

利用恒等式构造, 考虑立方差: $$(i+1{)}^3-i^3=3i^2+3i+1$$

两边从$i=1$到$n$求和:

左边是望远镜和: $$\begin{array}{rl}\sum _{i=1}^n\left[(i+1{)}^3-i^3\right]& =(n+1{)}^3-1^3\\ & =n^3+3n^2+3n\end{array}$$

右边: $$\begin{array}{rl}\sum _{i=1}^n(3i^2+3i+1)& =3\sum i^2+3\sum i+\sum 1\\ & =3S_2+3\cdot \frac{n(n+1)}{2}+n\end{array}$$

所以: $$n^3+3n^2+3n=3S_2+\frac{3n(n+1)}{2}+n$$

解这个方程求 $S_2$, 得: $$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$

立方和公式

同样用类似方法, 考虑四次方差: $$(i+1{)}^4-i^4=4i^3+6i^2+4i+1$$

左边望远镜: $$\begin{array}{rl}\sum _{i=1}^n\left[(i+1{)}^4-i^4\right]& =(n+1{)}^4-1\\ & =n^4+4n^3+6n^2+4n\end{array}$$

右边: $$\begin{array}{rl}4\sum i^3+6\sum i^2+4\sum i+\sum 1& =4S_3\\ & +6\cdot \frac{n(n+1)(2n+1)}{6}\\ & +4\cdot \frac{n(n+1)}{2}+n\end{array}$$

解得: $$\begin{array}{rl}\sum _{i=1}^n{i}^3& ={\left(\frac{n(n+1)}{2}\right)}^2\\ & =\frac{n^2(n+1{)}^2}{4}\end{array}$$

Warning

该章节仍在编写, 欢迎在 GitHub仓库 提交PR贡献内容.

编程中使用

pub fn sigma_sum(start: i32, end: i32, f: impl Fn(i32) -> i32) -> i32 {
    // 这里利用rayon还可以并行计算, 对大数据很有用
    (start..=end)   // 生成一个包含结束值(闭合)的迭代器
        .map(f)     // 对迭代器每一个项获取求和数据
        .sum()      // 完成求和
}

// example-test
sigma_sum(1, 5, |x| x * x)  // 输出1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 + 5 ^ 2的和

对于算术级数可以利用高斯求和, 时间复杂度从$\Theta (n)$降低到$\Theta (1)$:

pub fn gauss_sum(start: i64, end: i64) -> i64 {
    // 先除后乘, 防止中间溢出
    if (start + end) % 2 == 0 {
        (start + end) / 2 * (end - start + 1)
    } else {
        (end - start + 1) / 2 * (start + end)
    }
}

1. 级数是无穷数列的和. 即形如: ${\sum }_{i=1}^{\infty }{a}_i=a_1+a_2+\dots$ ↩

2. “等差级数“在无穷情形下通常不被视为严格定义的级数, 除非明确讨论其发散性. ↩