調和級数などのはなし - Qiita

今日は、競プロの計算量解析でよく出てくる、調和級数と割り算で出てくる項数の話をします。 計算量解析に失敗すると、実は解ける解法なのに解析に失敗したせいで解けないと思い込んでしまい、解かなかった、みたいなことが起こりかねないので、特に非直感的なこの2つについて押さえておきましょう。 調和級数とは、$\sum_{n=1}^k \frac{1}{n}$ で表される級数です。 $k \rightarrow \infty$ とした時に正の無限大に発散することが知られていますが、発散は非常に遅いです。 さて、この調和級数は計算量解析にしばしば登場します。 1からNまでの間隔で長さNの数列を見ていく、みたいな処理の計算量見積もりには調和級数に関する知識が欠かせません。 先ほど述べたように調和級数の発散は非常に遅く、先頭 $N$ 項までの和は $\log N+1$ より小さいことが知られています。以下にこ