定义
调和级数 : \(\sum\limits^{\infty}_{i=1}{\frac{1}{i}}\)
\(f_n=\sum\limits^{n}_{i=1}{\frac{1}{i}}\)
计算
\(f_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{6} + \dotsm + \frac{1}{n} < 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \dotsm + 1 = O(\ln n)\)
即 \(f_n = O(\ln n)\)
实际上 \(f_n = \ln n + \gamma + o(\frac{1}{2n})\) ,其中 \(\gamma = 0.57721 56649 01532 86060 65120 90082 40243 10421 59335 \dotso\) ,是欧拉常数。
当 \(n \rightarrow \infty, f_n = \ln n + \gamma\)
代码实现:
- 当 \(n\) 比较小的时候可以按定义式计算 \(f_n\) ,尽量不要用 \(\ln n + \gamma\) 来算,因为有 \(o(\frac{1}{2n})\) 的误差
- 当 \(n\) 比较大的时候直接计算 \(\ln n + \gamma\)
例题
设 \(g_n\) 为 \(\text{work}(n)\) 的期望值
\[g_n = \begin{cases} 1 + \frac{1}{n}\sum\limits^n_{i=1}{g_i} & n > 1 \\ 0 & n = 1 \end{cases} \]对于 \(n > 1\)
\(g_n = 1 + \frac{1}{n}\sum\limits^n_{i=1}{g_i}\)
\(n \times g_n = n + \sum\limits^n_{i=1}{g_i}\)
\((n - 1) \times g_n = n + \sum\limits^{n-1}_{i=1}{g_i}\) \((1)\)
换元 \(n \leftarrow n - 1\)
\((n - 2) \times g_{n-1} = n - 1 + \sum\limits^{n-2}_{i=1}{g_i}\) \((2)\)
\((1)\) 式 \(-\) \((2)\) 式,得
\((n - 1) \times g_n - (n - 2) \times g_{n-1} = 1 + g_{n-1}\)
\(g_n = g_{n-1} + \frac{1}{n-1}\)
则
\[g_n = \begin{cases} f_n + 1 & n > 1 \\ 0 & n = 1 \end{cases} \] 标签:frac,limits,ln,sum,调和级数,times,gamma From: https://www.cnblogs.com/kuailedetongnian/p/18246817