对于输入大小为n，哪些n值下插入排序会胜过归并排序？

Question

在《算法导论》（Corman）一书中，练习1.2-2提出了关于比较插入排序和归并排序实现的问题。对于输入大小为n，插入排序运行了8n^2次步骤，而归并排序运行了64n lg n次步骤; 对于哪些n值，插入排序能够击败归并排序？

虽然我对答案很感兴趣，但我更想知道如何逐步找到答案（以便我可以重复这个过程来比较任何给定的算法，如果可能的话）。

乍一看，这个问题似乎类似于在商务微积分中找到盈亏平衡点，我在5年前学过这门课程，但我不确定，所以任何帮助都将不胜感激。

谢谢

P / S 如果我的标签不正确，此问题被错误分类或其他约定被滥用，请尽量减少责备，因为这是我第一次发布问题。

- Nate Neuhaus

---

8n^2=64nlgn的解为n=44。因此，对于43个或更少的元素，请使用插入排序，否则请使用归并排序。 - arunmoezhi

@arunmoezhi 这里的8n^2和64nlogn是实际存在的值吗？还是只是问题陈述中的假设值？ - aandis

@zack提出了这些值的问题。 - arunmoezhi

Answer 1

由于您需要找出何时插入排序胜过归并排序

8n^2<=64nlogn
n^2<=8nlogn
n<=8logn

解 n-8logn = 0 可得：

n = 43.411

因此，对于 n<=43 ，插入排序比归并排序更有效。

- aandis

---

谢谢你的帮助，由于我的声望不足+15，我无法给你点赞。有人可以点赞吗？;) - Nate Neuhaus

您可以通过点击上方赞成按钮下面的绿色勾号来接受我的答案。 - aandis

谢谢您，顺便问一下，对数的底是多少？我对这个材料非常陌生，正在自学。 - Nate Neuhaus

说实话，我并没有完全理解结尾，虽然我想这是因为我几乎忘记了所有的微积分（哈哈），所以我没有进一步询问数学问题，而是将问题的那一部分重新发布在这里，结果被告知答案是错误的，我引用一下：“不是真的：43.11 > 8*log(43.11) = 30.11。”有什么想法吗？ - Nate Neuhaus

既然你提到了，我记得读过这个，但是这次讨论让我更好地理解了。所以，如果你不介意的话，你能告诉我你是如何从n-8logn = 0推导出最终答案n = 43.411的吗？你使用了Lambert W函数吗？ - Nate Neuhaus