对于大小为n的输入,n的值是插入排序节拍合并排序吗？

Question

在"算法简介"(Corman)一书中,练习1.2-2询问了有关比较插入排序和合并排序实现的以下问题.对于大小为n的输入,插入排序以8n ^ 2步进行,而合并排序以64n lg n步进行; n的值是插入排序节拍合并排序？

虽然我对答案感兴趣,但我更感兴趣的是如何逐步找到答案(这样我就可以重复这个过程来比较任何两个给定的算法,如果可能的话).

乍一看,这个问题看起来类似于找到商业微积分中的收支平衡点,这是我5年多前的一个课程,但我不确定所以任何帮助都会受到赞赏.

谢谢

P/S如果我的标签不正确,这个问题被错误分类,或者其他一些惯例被滥用,请将惩罚限制在最低限度,因为这是我第一次发帖提问.

Answer 1

因为你要找到插入排序节拍合并排序

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

在解决n-8logn = 0你得到

n = 43.411

因此对于n<=43插入排序比合并排序更好.