为什么K子集划分问题所用贪心算法的时间复杂度为O(n log(n))

我们可以把该算法的执行过程拆分为两个独立步骤分别计算时间复杂度，最终合并得到总复杂度：

• 第一步：对多重集S的n个元素做降序排序
  不管用快速排序、归并排序还是编程语言自带的通用排序实现，基于比较的排序算法的时间复杂度上界都是O(n log n)，这是该算法时间复杂度的主要组成部分。
• 第二步：遍历排序后的元素，逐个分配到当前和最小的子集中
  常规的高效实现会用最小堆（优先队列）存储K个子集的当前和：
  1. 每次查询当前最小子集和的操作是堆顶查询，时间复杂度O(log K)
  2. 将当前元素加入对应子集后，更新堆中该子集的和、重排堆的时间复杂度也是O(log K)
  3. 总共要处理n个元素，这一步总时间复杂度为O(n log K)
• 总复杂度合并逻辑
  因为子集数K的取值不可能超过元素总数n（极端情况每个子集仅含1个元素），所以log K ≤ log n恒成立，因此O(n log K)的上界是O(n log n)，和排序步骤的复杂度合并后，总时间复杂度的上界就是O(n log n)。

补充说明：如果不用最小堆优化，每次遍历K个子集找最小和，这一步的时间复杂度是O(nK)，只有当K为常数或者远小于log n时，总复杂度才保持O(n log n)，因此用最小堆实现是该算法保证稳定达到*O(n log n)*复杂度的前提。

内容的提问来源于stack exchange，提问作者Ahmad Shabani