挿入ソートとマージソートの問題を解いているのですが、
途中で行き詰ってしまいました。
(問題文)
サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、
マージソートの実行には64nlnnステップかかる。
挿入ソートがマージソートに勝るnの値を求めよ。
補足:ln=eを底とするlog
(挿入ソートがマージソートに勝る=挿入ソートがマージソートより実行時間が早い)
8n~2 <= 64nlnn
8lnn=n
e~n=n~8
こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。
どなたかご教授いただける方いましたらよろしくお願いします。
No.3ベストアンサー
- 回答日時:
数学の方で質問を見てどういう背景かと思いましたが、こういう問題だったのですね。
問題からすると自然対数(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
- 回答日時:
挿入ソートは 計算量(オーダ)がO(N^2)のアルゴリズム,マージソートは O(N×log2N)のアルゴリズムとして知られていますから,Nが大きくなるほどマージソートが速い。
ということで,挿入ソートの方が勝る例があり得るなら,Nがある値以下のときということになります。
8lnN=N,という式をどう解くか,というのは,コンピューター分野にこだわらない,数学の問題だと思います。私はてんで数学音痴なので,それをどう解くのか,きれいに求める方法は存在しないのか,さっぱり分かりません。
数学カテゴリの方で助力を仰いでみてはいかがでしょう。
(この問題,私も興味があります。解けるのなら,私にも教えていただきたいなあ)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
首吊りどこ締めるの
-
彼女のことが好きすぎて彼女の...
-
白血球が多いとどんな心配があ...
-
勃起する時って痛いんですか? ...
-
風俗店へ行く前のご飯
-
イタリアから帰国する際、肉製...
-
甲状腺が腫れているが血液検査...
-
エクセル指定した範囲からラン...
-
精子が黄色?
-
これって喉仏ですか? 私は女性...
-
EXCELで条件付き書式で空白セル...
-
精子に血が・・・
-
急に主人の性欲が強くなった
-
一番多く表示のある値(文字列...
-
精液の落とし方を教えてください
-
エクセルで数式の答えを数値と...
-
2つの数値のうち、数値が小さい...
-
テスターで断線を調べる方法教...
-
VLOOKUP関数を使用時、検索する...
-
検便についてです。 便は取れた...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
首吊りどこ締めるの
-
彼女のことが好きすぎて彼女の...
-
白血球が多いとどんな心配があ...
-
勃起する時って痛いんですか? ...
-
精子が黄色?
-
検便についてです。 便は取れた...
-
これって喉仏ですか? 私は女性...
-
小数点以下を繰り上げたものを...
-
甲状腺が腫れているが血液検査...
-
精液の落とし方を教えてください
-
エクセル指定した範囲からラン...
-
EXCELで条件付き書式で空白セル...
-
2つの数値のうち、数値が小さい...
-
精子に血が・・・
-
エクセルのラベルの値(文字列...
-
イタリアから帰国する際、肉製...
-
ある範囲のセルから任意の値を...
-
リンク先のファイルを開かなく...
-
中出しをするとお腹が痛い・・・。
-
MIN関数で空白セルを無視したい...
おすすめ情報