イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

58. 調和級数がだいたい log N で押さえられる話

数学

今日こちらの問題を解いていて、途中で調和級数的なものが出てきました。

atcoder.jp

 

この問題自体は残念ながら O(N^2) までしか落とせなくて自力では解けなかったのですが、 O(N\log N) へ落とす発想として色々弄っていると調和級数的なものが出てきたのでした。

調和級数とは以下のようなものです。

 \displaystyle \sum_{k=1}^{\infty} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots
 
競プロで無限級数は扱わないので、以下のように N までを考えます。
 \displaystyle \sum_{k=1}^{N} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots + \frac{1}{N}
 
これが O(\log N) であることが知られています。つまり、 N が増加する速度に比べて、調和級数が増加する速度は非常に遅いです。

ibako-piyo.hatenablog.com

 

対数で押さえられることは自分で解いていて証明できたのですが、後でネットで検索してよく出てくる方法と違っていたので「こういう考え方もあるよ」ということで記事を書いてみます。

よくある証明は、積分を使って面積から近似する方法みたいです。

examist.jp

 

自分が考えていたときは「とりあえず上界が分かれば良いや」くらいのものだったので、そこまで厳密に考えず、以下のような式変形で対数で押さえられることに気付きました。

 \begin{eqnarray} \displaystyle \sum_{k=1}^{N} \frac{1}{k} & = & 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \cdots + \frac{1}{N} \\\ \displaystyle & \le & 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \cdots + \frac{1}{2^{\log N}} \\\
\displaystyle & = & 1 + 1 + 1 + 1 + \cdots + 1 \\\
\displaystyle & = & 1 + \log N \end{eqnarray}

 

色々雑ですが、とりあえず対数で押さえられるんだなー、くらいのイメージを持つならこれで良いんじゃないかと思います。