我想对合并排序进行修改，其中 n/k 个长度为 k 的子列表使用插入排序进行排序，然后使用合并排序的标准合并机制进行合并。我想知道合并排序的修改版本的 k 值必须等于多少，以在朗姆时间复杂度方面等于合并排序的原始版本。这是我自己的概念练习。代码和/或解释表示赞赏。
问问题
405 次
1 回答
0
Your n/k-way merge is O(n^2/k) (explanation here). Each of your individual insertion sorts are O(k^2). Observe that for any value of k, your overall running complexity will remain O(n^2); therefore, no value of k will allow your modified merge sort to be O(nlogn)
于 2013-10-23T05:44:55.493 回答