私が読んでいるアルゴリズムの本からの質問があり、それを解決する方法に困惑しています (対数または指数の計算を行ってから長い時間が経ちました)。問題は次のとおりです。
同じマシンで挿入ソートとマージソートの実装を比較しているとします。サイズ n の入力の場合、挿入ソートは 8n^2 ステップで実行され、マージ ソートは 64n log n ステップで実行されます。挿入ソートがマージソートに勝る n の値はどれですか?
対数は 2 を底とします。私は等式を解こうと試み始めましたが、n = 8 log n 付近で行き詰まります。
これを数学的に解決する方法について議論する答えが欲しいです（Excelでのブルートフォースは容認できません;））。対数計算の説明へのリンクは、あなたの答えを理解するのにも非常に役立ちます。
前もって感謝します！
http://www.wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29 （古いリンクが機能しなくなったため編集）
最善の策は、ニュートン法を使用することです。
これを解決するための1つの手法は、グラフ電卓をつかんで両方の関数をグラフ化することです（別の回答のWolframリンクを参照してください）。興味のある交差点を見つけます（例のように複数の交差点がある場合）。
いずれにせよ、n = 8log₂nを解くための簡単な式はありません（私が知る限り）。質問を次のように言い換える方が簡単かもしれません：「f（n）=n-8log²nのゼロを見つけてください」。まず、関心のある交差点を含む領域を見つけて、その領域を縮小し続けます。たとえば、ターゲットnが42より大きく、44より小さいことがわかっているとします。f（42）は0未満で、f（44）は0より大きいです。f（43）を試してください。0未満なので、43.5を試してください。まだ0未満なので、43.75を試してください。0より大きいので、43.625を試してください。0より大きいので、下に移動し続けます。この手法は二分探索と呼ばれます。
申し訳ありませんが、これは「Excelを使用したブルートフォース」のバリエーションにすぎません:-)
編集：
それを楽しむために、私は二分探索でこの問題を解決するスプレッドシートを作成しました：binary‑search.xls。二分探索ロジックは2番目のデータ列にあり、私はそれを自動拡張しました。