挿入ソートとマージソート

質問

挿入ソートとマージソートの問題を解いているのですが、
途中で行き詰ってしまいました。

（問題文）
サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、
マージソートの実行には64nlnnステップかかる。
挿入ソートがマージソートに勝るnの値を求めよ。
補足：ln=eを底とするlog

（挿入ソートがマージソートに勝る＝挿入ソートがマージソートより実行時間が早い）
8n~2 <= 64nlnn
8lnn=n
e~n=n~8

こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。
どなたかご教授いただける方いましたらよろしくお願いします。

回答No.3

rinkun · ベストアンサー

数学の方で質問を見てどういう背景かと思いましたが、こういう問題だったのですね。
問題からすると自然対数(ln)ではなく2を底とする対数(lg)と考えた方が自然なのですけど、自然対数で間違いないのでしょうか。

lgなら
8*n*n<=64*n*lg(n)
から
1/8<=lg(n)/n
だから、右辺を評価して
2<=n<=43

lnなら
1/8<=ln(n)/n
だから、数学の方の質問に回答されているように
2<=n<=26
です。

lgでもlnでも割り切れる計算にはならないので、グラフを書いて範囲を絞り、整数nについて評価して範囲を確定するしかないですね。

お礼

非常にわかりやすい回答ありがとうございました。
先日、授業で解答を得たところrinkunさんの解答とほぼ同じでした。
参考になりました。

回答No.2

jjon-com

挿入ソートは 計算量（オーダ）がＯ(Ｎ^2)のアルゴリズム，マージソートは Ｏ(Ｎ×log2Ｎ)のアルゴリズムとして知られていますから，Ｎが大きくなるほどマージソートが速い。
ということで，挿入ソートの方が勝る例があり得るなら，Ｎがある値以下のときということになります。

８lnＮ＝Ｎ，という式をどう解くか，というのは，コンピューター分野にこだわらない，数学の問題だと思います。私はてんで数学音痴なので，それをどう解くのか，きれいに求める方法は存在しないのか，さっぱり分かりません。

数学カテゴリの方で助力を仰いでみてはいかがでしょう。
（この問題，私も興味があります。解けるのなら，私にも教えていただきたいなあ）

回答No.1

Tacosan

その式が正しいなら, そこから先の「きれいに求める方法」は存在しないです. n にあたりをつけてなんとか計算していくしかないと思う.