runtime - 挿入ソートはマージソートよりも速いのはいつですか？

Question

宿題の問題については、挿入ソートは8n ^ 2で実行され、マージソートは64（n（lg n））で実行されると言われました。私が与えられた解決策の一部として、挿入ソートはマージソートよりもn <= 43である限り高速であると言われましたが、先生の答えは、なぜ、またはどのようにして43に到達したのかを実際には説明していません。私は実行時間を把握するのが苦手なので、理解を深めようとしています。はい、先生に聞いてみましたが、それでも戸惑いました。どんな助けでも素晴らしいでしょう！ありがとう！

Answer 1

それは、この(代数的)推論の行から来ました

steps_in_insertion_sort <= steps_in_merge_sort
8n^2 <= 64n lg n
n^2 <= 8n lg n
n <= 8 lg n

次に、43 は試行錯誤によって、または方程式 n - 8 lg n = 0 のゼロを解くことによって機能します。

試行錯誤によるハッキングについては、次の点に注意してください。

$ python
>>> 8 * log(43)/log(2)
43.41011803761678

「lg」は対数底 2 を意味するためです。

(余談ですが、このような計算は、あるアルゴリズムが別のアルゴリズムを打ち負かすという現実世界の兆候には実際には変換されません。真剣に、正確に 43?)

Answer 2

これは、コーメンによるアルゴリズム入門、第 3 版の 2 番目の演習問題です。この方程式の解は、アルゴリズムの初心者にとってそれほど単純ではありません。

8n^2 < 64n lg n 、n < 8 lg n 、2^ n/8 < n の場合、挿入ソートはマージソートよりも優先されます。これは、2 <= n <= 43 の場合に当てはまります (電卓を使用して求められます)。したがって、実行時間を改善するために、サイズ 43 以下の入力に対して挿入ソートを使用するようにマージソートを書き換えることができます。