計算量とオーダー記法ランダウの記法、対数関数、積分、区分求積法、級数、不等式

学習環境

開発環境

問題解決力を鍛える!アルゴリズムとデータ構造 (大槻兼資(著)、秋葉拓哉(監修)、講談社)の第2章(計算量とオーダー記法)、章末問題2.6の解答を求めてみる。

不等式

\int_{1}^{N + 1} \frac{1}{x} dx \leq \sum_{k = 1}^{N} \frac{1}{x} \leq 1 + \int_{1}^{N} \frac{1}{x} dx

が成り立つ。

よって、

\begin{array}{l} {[\log x]}_{1}^{N + 1} \leq \sum_{k = 1}^{N} \frac{1}{x} \leq 1 + {[\log x]}_{1}^{N} \\ \log (N + 1) \leq \sum_{k = 1}^{N} \frac{1}{k} \leq 1 + \log N \end{array}

ゆえに、

\sum_{k = 1}^{N} \frac{1}{k} = O (\log N)

が成立する。

実際に確認してみる。

コード

package main

import (
	"fmt"
	"math"
)

func sum(n float64) float64 {
	t := 0.0
	for i := 1.0; i <= n; i++ {
		t += 1.0 / i
	}
	return t
}
func main() {
	for n := 1.0; n <= 20; n++ {
		l := math.Log(n + 1)
		c := sum(n)
		r := 1 + math.Log(n)
		fmt.Printf("%.2f <= %.2f <= %.2f: %v\n", l, c, r, l <= c && c <= r)
	}
}

入出力結果

% go run ./main.go
0.69 <= 1.00 <= 1.00: true
1.10 <= 1.50 <= 1.69: true
1.39 <= 1.83 <= 2.10: true
1.61 <= 2.08 <= 2.39: true
1.79 <= 2.28 <= 2.61: true
1.95 <= 2.45 <= 2.79: true
2.08 <= 2.59 <= 2.95: true
2.20 <= 2.72 <= 3.08: true
2.30 <= 2.83 <= 3.20: true
2.40 <= 2.93 <= 3.30: true
2.48 <= 3.02 <= 3.40: true
2.56 <= 3.10 <= 3.48: true
2.64 <= 3.18 <= 3.56: true
2.71 <= 3.25 <= 3.64: true
2.77 <= 3.32 <= 3.71: true
2.83 <= 3.38 <= 3.77: true
2.89 <= 3.44 <= 3.83: true
2.94 <= 3.50 <= 3.89: true
3.00 <= 3.55 <= 3.94: true
3.04 <= 3.60 <= 4.00: true
%