在《算法简介》(Corman)一书中,练习1.2-2提出了以下有关比较插入排序和合并排序的实现的问题。对于大小为n的输入,插入排序以8n ^ 2的步长运行,而合并排序以64n lg n的步长运行;插入排序优于n的哪些值进行合并排序?
尽管我对答案很感兴趣,但是我对如何逐步找到答案更感兴趣(以便我可以重复此过程以尽可能比较任何两个给定算法)。
乍一看,这个问题似乎类似于在业务演算中找到盈亏平衡点,这是我五年多以前上的一堂课,但是我不确定是否会有任何帮助。
谢谢
P / S如果我的标签不正确,此问题的分类不正确,或者此处滥用了其他约定,请限制降级为最低,因为这是我第一次发布问题。
由于您将发现插入排序优于合并排序
8n^2<=64nlogn n^2<=8nlogn n<=8logn
在解决n-8logn = 0你得到
n-8logn = 0
n = 43.411
因此,对于n<=43插入排序,比合并排序更好。
n<=43