权当数据结构与算法分析的学习手记
系数为一的幂级数部分和公式
- ∑ n2 = 12 + 22 + 32 + ... + n2 = n(n+1)(2n+1)/6 = O(n3)
- ∑ n3 = 13 + 23 + 33 + ... + n3 = n2(n+1)2/4 = O(n4)
- ∑ n4 = 14 + 24 + 34 + ... + n4 = n(n+1)(2n+1)(3n2+3n-1)/30 = O(n5)
调和级数与对数级数
- 调和级数: 1+1/2+1/3+1/4+...+1/n = ⊙(log n)
- 对数级数: log1+log2+log3+...logn = log(n!) = ⊙(nlog n)
收敛级数
- 一般都为O(1)
- 例如:1+1/22+1/32+1/42+...+1/n2 = 6/π2 = O(1)