Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
认识调和级数
? 原创 ?
2018-11-13 09:25:17
658
0
0
rockdu
? 原创 ?
原来一直只把调和级数($H_n$)当成算复杂度的工具。 直到遇到了这样一道题： [T2062 随机数生成器](https://www.luogu.org/problemnew/show/T2062) 通过打表可以发现，答案就是$H_n+1$ 但是$n$太大，调和数本身也没有通项公式。 在说这道题之前，我们先来说说调和数是什么吧。 $$H_n=1+\frac{1}{2}+\frac{1}{3}+...=\sum^n_{k=1}\frac{1}{k}$$ 平时我们计算复杂度的时候经常说$H_n$是$ln(n)$级别的 其实这是一个比较准确的估计，因为欧拉给出了以下结论： $$lim_{n\to \infty}(H_n-ln(n))=\gamma $$ 其中$\gamma$是欧拉常数，已知: $\gamma \approx 0.5772156649........$ 更令人惊喜的是，这个无穷级数不仅是收敛的，而且收敛的非常快。 因此，在$n$十分大的时候，我们可以直接获得$H_n$十分精确的值。 $$H_n = ln(n)+\gamma$$ 上面的那道题也就迎刃而解了~
上一篇:
洛谷P2403 [SDOI2010]所驼门王的宝藏
下一篇:
洛谷P1979 华容道
0
赞
658 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册