假设给定一个包含 n 个元素的序列进行排序。输入序列由 n/k 个子序列组成，每个子序列包含 k 个元素。给定子序列中的元素都小于后续子序列中的元素并且大于前面子序列中的元素。因此，对长度为 n 的整个序列进行排序所需的只是对 n/k 个子序列中的每个子序列中的 k 个元素进行排序。显示求解该排序算法变体所需的比较次数的 Ω(n lg k) 下限。（提示：简单地组合各个子序列的下界并不严格。）
需要提示，不确定如何处理。在我的书中，我们介绍了对我来说有意义的决策树模型。
假设给定一个包含 n 个元素的序列进行排序。输入序列由 n/k 个子序列组成，每个子序列包含 k 个元素。给定子序列中的元素都小于后续子序列中的元素并且大于前面子序列中的元素。因此，对长度为 n 的整个序列进行排序所需的只是对 n/k 个子序列中的每个子序列中的 k 个元素进行排序。显示求解该排序算法变体所需的比较次数的 Ω(n lg k) 下限。（提示：简单地组合各个子序列的下界并不严格。）
需要提示，不确定如何处理。在我的书中，我们介绍了对我来说有意义的决策树模型。