数列和

Last Updated: 2024-04-14 13:38:30 Sunday

-- TOC --

研究算法理论,需要用数学工具来证明的。在一众可能会用到的数学工具中,数列必不可少,我们常常通过数列和,证明时间或空间复杂度。

无穷级数与数列和

计算机科学中遇到的很多都不是级数,只是有限项的数列和

Sum of Odds

$$\sum_{k=1}^n(2k-1)=n^2$$

可以用Induction的方法证明,可以更直接的用Picture Proof的方法证明,一图胜千言,没办法,人类就进化成这样了。关于奇数和的这个公式的证明,如下图:

odd_sum.png

Arithmetic Series(等差数列)

$$\sum_{i=1}^ni=\cfrac{n(n+1)}{2}=\Theta(n^2)$$

Sum of Squares

$$\begin{align} \sum_{k=1}^n{k^2} &= 1^2+2^2+3^2+...+n^2\notag \\ &= \cfrac{2 n^3 + 3 n^2 + n}{6}\notag \\ &= \cfrac{n(n+1)(2n+1)}{6}\notag \end{align}$$

可用Induction证明,但不知道最初是怎么得到这个结果的...?

Sum of Cubes

$$\sum_{i=1}^ni^3=\cfrac{n^2(n+1)^2}{4}$$

Geometric Series(等比数列)

$$\sum_{k=0}^n a^k = 1+ a + a^2 + ... + a^n = \frac{1-a^{n+1}}{1-a},(a\neq1) $$

The sum of any geometric series is a constant times its largest term. (找出最大项,这本就是得到asymptotic notation的方法,更是不是geometric seires貌似没关系)

推导方法

设\(S=\sum_{k=0}^{n}\),然后计算\(S-aS\)。

这种方法对于计算有限项数列和是OK的,如果是无限项,S就成了无穷级数的部分和,S必须要收敛!否则计算结果会很荒谬...

Picture Proof

$$a=\cfrac{1}{2}$$

geometric_series.png

当\(a=2\)时

$$\sum_{k=0}^n2^k=2^{n+1}-1$$

此时如果是无穷级数,S发散,是无法计算的。

Harmonic Series(调和数列)

For positive integer n, the nth harmonic number is:

$$H_n=\sum_{i=1}^n\cfrac{1}{i} = \ln{n} + O(1)$$

调和级数是发散的...

积和转换

$$\sum_{i,j}a_ia_j=\left(\sum_ia_i\right)^2$$

大量的乘法就这样消散,用加法取代,计算速度极快!从\(\Theta(n^2)\)到\(\Theta(n)\)。

示例1:

$$\begin{aligned} \sum_{i,j}a_ia_j(j-i)^2 &= \sum_{i,j}a_ia_j(j^2-2ija_ia_j+i^2)\\ &=\sum_{i,j}a_ia_jj^2 - 2\sum_{i,j}ij\cdot a_ia_j + \sum_{i,j}a_ja_ii^2\\ &=2\left(\sum_{i}a_i\cdot\sum_{i}a_i\cdot i^2 - \left(\sum_ia_i\cdot i\right)^2\right) \end{aligned}$$

对应算法代码:

fastsum.png

示例2:

$$\begin{aligned} \sum_{i}\sum_{m}a_ia_me^{i+m}&=\sum_{i,m}a_ie^i\cdot a_me^m \\ &=\left(\sum_{i}a_ie^i\right)^2 \end{aligned}$$

本文链接:https://cs.pynote.net/math/202401316/

-- EOF --

-- MORE --