在合并排序中插入排序的最坏情况是什么时间？

Question

最近我从算法导论第3版偶然发现了这个问题。

问题2-1:

虽然合并排序在O(n logn)最坏情况下运行，插入排序在O(n^2)中运行，但对于小问题大小，后者运行得更快。考虑对合并排序的修改，其中n/k长度为k的子列表使用插入排序排序，然后使用标准合并机制进行合并。

(A)显示插入排序可以在O(nk)最坏情况下对长度为k的n/k子列表进行排序。

答案是：

Ans:在最坏的情况下，插入排序每个k元素列表需要(k^2)时间。因此，对k个元素的n/k列表进行排序需要(k^2n/k)= (nk)最坏情况时间。

他们如何从给定的数据中得到(k^2n/k)？我一点也不明白这一点，我很想得到一个解释。

Answer 1

子列表的长度为k，因此插入排序对每个子列表采用k^2。现在，总共有n/k子列表，所以，n/k * k^2是nk。这里的关键理解是有n/k数量的子列表，插入排序需要k^2时间来对每个子列表进行排序。

另外要注意的是，知道合并排序有O(n logn)实际上对这个问题并不重要，因为他们没有要求对整个列表排序的时间，只需要对所有子列表进行排序的时间。