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

Question

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

问题2-1：

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

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

---

给出的答案是：

Ans：在最坏的情况下，插入排序每个 k 元素列表需要 (k^2) 时间。因此，对 k 个元素的 n/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)实际上对这个问题根本不重要，因为他们不要求对整个列表进行排序的时间，而只是要求对所有子列表进行排序的时间。