5. 求和引论¶

5.1. 求和¶

大多数程序都包含循环结构。在分析带循环程序的运行时间代价时，我们需要把循环每次执行的代价累加起来。这是求和的一个例子。求和不过是对某个函数作用于一定范围参数值的代价之和。求和通常用下面的 "Sigma" 记号书写：

\[\sum_{i=1}^{n} f(i).\]

该记号表示我们在某个（整数）值范围内对 \(f(i)\) 的取值求和。表达式的参数及其初始值标在 \(\sum\) 符号下方。这里，记号 \(i=1\) 表示参数是 \(i\) ，且其初值为 1。 \(\sum\) 符号上方是表达式 \(n\) 。这表示参数 \(i\) 的最大值。因此，该记号表示当 \(i\) 遍历从 1 到 \(n\) 的整数时，对 \(f(i)\) 的取值求和。这也可以写作 \(f(1) + f(2) + \cdots + f(n-1) + f(n)\) 。在句子中，Sigma 记号排版为 \(\sum_{i=1}^{n} f(i)\) 。

给定一个求和，你常常希望用一个与求和值相同的代数方程来替换它。这称为闭式解，而用闭式解替换求和的过程称为求解该求和。例如，求和 \(\sum_{i=1}^{n} 1\) 就是把表达式 "1" 求和 \(n\) 次（记住 \(i\) 从 1 取到 \(n\) ）。因为 \(n\) 个 1 之和为 \(n\) ，所以闭式解是 \(n\) 。

下面解释本书中将多次出现的一个求和的闭式解。由于它出现得如此频繁，如果你能对它感到自如，日后会很有帮助。

Settings

Saving...

Server Error
Resubmit

Settings

Saving...

Server Error
Resubmit

下面是常用求及其闭式解的列表。

\[\begin{split}\sum_{i = 1}^{n} i &= \frac{n (n+1)}{2} \\ \sum_{i = 1}^{n} i^2 &= \frac{2 n^3 + 3 n^2 + n}{6} = \frac{n(2n + 1)(n + 1)}{6} \\ \sum_{i = 1}^{\log n} n &= n \log n \\ \sum_{i = 0}^\infty a^i &= \frac{1}{1-a}\ \text{for} \ 0 < a < 1 \\ \sum_{i = 0}^{n} a^i &= \frac{a^{n+1} - 1}{a - 1}\ \text{for} \ a \neq 1 \\ \text{As special cases to the last summation, we have the following two:} \ \sum_{i = 1}^{n} \frac{1}{2^i} &= 1 - \frac{1}{2^n} \\ \sum_{i = 0}^{n} 2^i &= 2^{n+1} - 1 \\ \text{As a corollary to the previous summation: } \ \sum_{i = 0}^{\log n} 2^i &= 2^{\log n + 1} - 1 = 2n - 1 \\ \text{Finally: } \ \sum_{i = 1}^{n} \frac{i}{2^i} &= 2 - \frac{n+2}{2^n}\end{split}\]

从 1 到 \(n\) 的倒数之和称为调和级数，写作 \({\cal H}_n\) ，其值介于 \(\log_e n\) 和 \(\log_e n + 1\) 之间。更精确地说，随着 \(n\) 增大，该求和越来越接近

\[{\cal H}_n \approx \log_e n + \gamma + \frac{1}{2n},\]

其中 \(\gamma\) 是欧拉常数，其值为 0.5772...

这些等式大多可以通过归纳法证明轻松证明。遗憾的是，归纳法并不能帮助我们推导出闭式解。归纳法只能确认所提议的闭式解是否正确。

CS3 数据结构与算法

Chapter 3 Mathematical Background

5. 求和引论¶

5.1. 求和¶