Search on the blog

2013年4月21日日曜日

1/xの和とlog x

とある問題をといているとき、計算量の見積りに



を使う場面があった。

log(x)は1/xの原始関数なのでまあそうなるのは分かるけど、xがどれくらい大きいと上式がどれくらいの正確さで成り立つのか実験してみた。

x log(x) sum(1/x)
1 0 1
10 2.303 2.929
100 4.605 5.187
1,000 6.908 7.485
10,000 9.210 9.788
100,000 11.51 12.09
1,000,000 13.82 14.39
10,000,000 16.12 16.70
100,000,000 18.42 19.00
1,000,000,000 20.72 21.30

そうか、いや、まあそうなるよね。。logだからね。
計算量の見積りという観点では、誤差とか気にするようなレベルではないか。

0 件のコメント:

コメントを投稿