您将获得一个由n个元素组成的序列进行排序。输入序列由n/k个子序列组成，每个子序列包含k个元素。给定子序列中的元素都小于后续子序列中的元素，且大于前一个子序列中的元素。因此，对长度n的整个序列进行排序所需的只是对每个n/k子序列中的k个元素进行排序。
null
解决这种排序问题所需的比较次数下限为 （A） Ω（n） （B） Ω（n/k） （C） Ω（nlogk） （D） Ω（n/klogn/k） 答复: （C） 说明： 我们有n/k个子序列，每个子序列包含k个元素。
如果我们使用快速排序技术对子序列中的k个元素进行排序，那么对子序列中的k个元素进行排序的复杂性是klogk。
我们有n/k个这样的序列。那么，具有k个元素的n/k个子序列的时间复杂度将为：
=（n/k）*klogk
=nlogk 这个问题的小测验
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
