一尘不染

对于大小为n的输入,insert-sort是否击败了merge-sort的n值?[关闭]

algorithm

在《算法简介》(Corman)一书中,练习1.2-2提出了以下有关比较插入排序和合并排序的实现的问题。对于大小为n的输入,插入排序以8n ^
2的步长运行,而合并排序以64n lg n的步长运行;插入排序优于n的哪些值进行合并排序?

尽管我对答案很感兴趣,但是我对如何逐步找到答案更感兴趣(以便我可以重复此过程以尽可能比较任何两个给定算法)。

乍一看,这个问题似乎类似于在业务演算中找到盈亏平衡点,这是我五年多以前上的一堂课,但是我不确定是否会有任何帮助。

谢谢

P / S如果我的标签不正确,此问题的分类不正确,或者此处滥用了其他约定,请限制降级为最低,因为这是我第一次发布问题。


阅读 226

收藏
2020-07-28

共1个答案

一尘不染

由于您将发现插入排序优于合并排序

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

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

n = 43.411

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

2020-07-28