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”的意思是 log-base-2。

(旁白:像这样的计算并不能真正转化为任何现实世界的迹象，表明一种算法将击败另一种算法。说真的，正好是 43？)