問題解決のための「アルゴリズム 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 はこんな単純に解けません。
小一時間数式をこねくり回していましたがダメでした・・・。
そうしたら下記のリンクのように、世の中には同じようなことをしている人がいるもので。
![](https://cdn.sstatic.net/Sites/math/Img/apple-touch-icon.png?v=0ae50baa40ed)
そのなかの回答の一つが「ニュートン法でも使ったら?」でした。
![](https://res.cloudinary.com/zenn/image/upload/s--U7iupB0n--/c_fit%2Cg_north_west%2Cl_text:notosansjp-medium.otf_55:%25E6%2596%25B9%25E7%25A8%258B%25E5%25BC%258F%25E3%2581%25AE%25E8%25A7%25A3%25E6%25B3%2595%25E3%2582%2592Python%25E3%2582%2592%25E4%25BD%25BF%25E3%2581%25A3%25E3%2581%25A6%25E8%25A7%25A3%25E3%2581%2584%25E3%2581%25A6%25E3%2581%25BF%25E3%2582%258B%25E3%2580%2590%25E3%2583%258B%25E3%2583%25A5%25E3%2583%25BC%25E3%2583%2588%25E3%2583%25B3%25E6%25B3%2595%25E3%2580%2591%2Cw_1010%2Cx_90%2Cy_100/g_south_west%2Cl_text:notosansjp-medium.otf_37:%25E3%2581%25A8%25E3%2582%2593%25E3%2581%25A8%25E3%2582%2593%25E3%2581%25BC%2Cx_203%2Cy_121/g_south_west%2Ch_90%2Cl_fetch:aHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyLzU2MGQzMzc3ZTQuanBlZw==%2Cr_max%2Cw_90%2Cx_87%2Cy_95/v1627283836/default/og-base-w1200-v2.png)
ありましたね、ニュートン法・・・。
(遠い学生時代の記憶)
流れとしては以下です。
まず漸化式
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 を見るに、近い結果が出ているのでそれなりに計算できていそうです。
しかし、解説のあっさりさ加減を見ると、もっと簡単に求められたんじゃないかなあ・・・?とは思いますね。
でもまあ、結果的に解けたので良しとしておきます。
コメント