問題解決のための「アルゴリズム x 数学」が基礎からしっかり身につく本の問題2.4.4、「N がどの程度の大きさであればおおよそ何回の計算を行うか」のところなのですが、N log N のところが全然分かりませんでした。
N^2、2^N の場合はどっちも明快で、例えば計算回数を 10^6 以内としたとき、
N^2 <= 10^6
N <= √10^6
N <= 10^3
N <= 1000
2^N <= 10^6
N log 2 <= log 10^6 (底は 10)
N log 2 <= 6 log 10
N <= 6 / log 2
N <= 19.931 <= 20
という感じになります。
一方、N log N はこんな単純に解けません。
小一時間数式をこねくり回していましたがダメでした・・・。
そうしたら下記のリンクのように、世の中には同じようなことをしている人がいるもので。
そのなかの回答の一つが「ニュートン法でも使ったら？」でした。
ありましたね、ニュートン法・・・。
(遠い学生時代の記憶)
流れとしては以下です。
まず漸化式
x_(n+1) = x_n – f(x_n) / f'(x_n)
上記は x = 0 のときの値を求めるものだから、
xlog(x) = 10^6 を xlog(x) – 10^6 = 0 にしておく。
その上で f(x) = xlog(x) – 10^6 の微分 f'(x) は (f(x)g(x))’ = f'(x)g(x) + f(x)g'(x) より、
f'(x_n) = (x log(x))’ = x’ log(x) + x (log(x))’ = 1*log(x) + x*(1/x) = log(x) + 1
以上より
x_(n+1) = x_n – f(x_n) / f'(x_n)
x_(n+1) = x_n – (xlog(x) – 10^6) / (log(x) + 1)
これを Python のプログラムに落とし込み、コミットしておきました。
演習問題 2.4.4 の N log N の際の N を求めるプログラム
https://github.com/men100/math-algorithm-book/commit/c9ef876617579ab5b8025b3e592264d9df1a67ff
上記のプログラムによって、計算した答えが以下。
10^6 のとき、 N <= 62746
10^7 のとき、 N <= 526172
10^8 のとき、 N <= 4523071
10^9 のとき、 N <= 39620077
解答の PDF を見るに、近い結果が出ているのでそれなりに計算できていそうです。
しかし、解説のあっさりさ加減を見ると、もっと簡単に求められたんじゃないかなあ・・・？とは思いますね。
でもまあ、結果的に解けたので良しとしておきます。
コメント