什么时候插入排序比合并排序快? [英] when is insertion sort faster than merge sort?

问题描述

对于一个作业问题，有人告诉我插入排序运行在8n ^ 2处，而合并排序运行在64(n(lg n))处.作为解决方案的一部分，我说插入排序比合并排序要快，只要n< = 43，但是老师的回答并不能真正解释他为什么或如何得出43.有人可以解释吗?我不太想弄清楚运行时间，所以我想更好地理解.是的，我试图问老师，但是我仍然很困惑.任何帮助将是巨大的！谢谢！

解决方案

它来自这一(代数)推理行

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"表示以日志为基础的两个.

(顺便说一句:这样的计算并不能真正转化为现实情况，表明一种算法将胜过另一种算法.说真的，就是43吗?)

For a homework problem, I was told that insertion sort runs at 8n^2 and that merge sort runs at 64(n(lg n)). As part of the solution I was given, it said that insertion sort was faster than merge sort as long as n <= 43, but the teacher's answer doesn't really explain why or how he arrived at 43. Can anyone explain this? I'm not that great with figuring out run times so I'm trying to get a better understanding. And yes, I tried asking the teacher, but I was still confused. Any help would be great! thank you!

解决方案

It came from this (algebraic) line of reasoning

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

Then 43 works by trial and error, or by solving for the zero of the equation n - 8 lg n = 0.

For hacking by trial and error, note:

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

Because "lg" means log-base-two.

(Aside: calculations like this do not really translate to any real-world indication that one algorithm will beat another. Seriously, exactly 43?)

这篇关于什么时候插入排序比合并排序快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！