algorithm - 合并排序中插入排序的最坏情况时间是多少？

Question

最近我从 Introduction To Algorithms Edition 3 偶然发现了这个问题

问题 2-1:

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

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

---

给出的答案是:

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

他们如何从给定数据中得到 (k^2 n​​/k)？我根本不理解这一点，非常感谢您的解释。

Answer 1

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

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