masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

アルゴリズムとデータ構造（けんちょん本）２．６

競技プログラミング高校数学

章末問題２．６

$y = \dfrac{1}{x}$ のグラフとその下側に作った長方形の面積を考える。
赤い長方形の面積は左から順に， $1, \dfrac{1}{2}, \dfrac{1}{3}, \cdots ,\dfrac{1}{10}$ となっている（縦横の比率がおかしいのは目をつぶる）。
$（赤い長方形の面積の和） \lt \int_1 ^N \dfrac{1}{x} dx + 1$ である。
ここで，
$\int _1 ^N \dfrac{1}{x} dx = \log N$ であるから，赤い長方形の面積の和< $\log N$ を得る。 f:id:masuTomo:20201006221522p:plain

以上のことから， $1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = O(\log N)$ であることがわかった。

おまけ

上記の図では， $y = \dfrac{1}{x}$ の下側の長方形の面積の和（不足和，Lower Sum）と積分値を比較したが，逆にグラフの上側にはみでるように長方形を作って，その長方形の和（過剰和, Upper Sum）を考えることで，上から抑えることもできる。下からも上からも評価できるので，結果として $1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = \Theta(\log N)$ がわかる。