Nlog2N=10^6の途中式について

質問

数学の対数およびアルゴリズムの計算量の勉強をしておりますが、

Nlog2N=10^6という式において
N≒60000となると記載があるのですが、
これはどういった展開でなるのでしょうか？

いくつかの公式を当てはめてみましたが、
上手く計算できませんでした。

もしくは、関数電卓を使わないと解けないレベル
なのでしょうか？

ご教授お願いいたします。

回答No.2

gamma1854 · ベストアンサー

まず、式をきちんと書いてください。
対数の底=2 として、次の意味で書いているとします。
N*log(N) = 10^6.
-------------
これを N にいて解く( N を平易な式で表現する) ことはできません。
そこで、この等式をみたす正数Nの近似値を求めることになります。
f(x) = x*log[2](x) - 10^6
とし、f(x)=0 となるｘのおおよその値は、次の漸化式を数回繰り返すことで得られます。
X[n+1] = {X[n] + 10^6*ln(2)}/{ln(X[n]) + 1}.
X[0]=60000 とすると、
1　x=62751.28440227821000
2　x=62746.12648728506000
3　x=62746.12646968824000
4　x=62746.12646968824000
5　x=62746.12646968824000

お礼

式の書き方についてはすいませんでした。
PC上での書き方についてわからなくて…

漸化式を利用して解くんですね。
どうりで式をいくら展開しても見やすくならないなと思ってました。
漸化式はまだ勉強していない部分だったので、勉強してから再度挑戦しようと思います。

ご回答ありがとうございました。

回答No.1

staratras

Nlog2N=10^6

上式をNについての方程式とみると、NlnN=10^6・ln2と変形して、厳密解はN=e^W(10^6・ln2)です。（lnはeを底とする自然対数）ここでWは「ランベルトのW関数」と呼ばれる関数で、普通の関数電卓にはありませんので、表計算ソフトのゴールシーク機能を使って近似解を求めるのが現実的でしょう。

LibreOffice Calc を用いて計算したらN≒62746.1264…になりました。

お礼

ご回答ありがとうございました。

まだ勉強していない部分があるようです。(eやランベルトのW関数など)
もう少し、勉強してから再度挑戦しようと思います。