求和意义和性质

当一个算法包含循环控制结构时，例如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$$ 用高斯求和，得 $$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}=\Theta (n^2)$$

该章节仍在编写，在 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. “等差级数”在无穷情形下通常不被视为严格定义的级数，除非明确讨论其发散性。 ↩