对集合进行分区并对分区的子集进行排序的时间复杂度

Question

假设我有一个函数，它将 S、|S|=n 集划分为 S/subsetSize 个大小为 subsetSize 的子集并对每个子集进行排序：

partitionAndSort(Set s, int subsetSize) {
   List partition = partitionList(s);
   for(Set subset: partition) {
      sort(subset);
   }
}

函数的运行时间是多少？

partition 显然需要 O(n) 因为我们一个一个地遍历集合的元素。 subsetSize 被认为是常数，因此单个排序需要 O(subsetSize*log(subsetSize))=O(1)，并且有 O(n/subsetSize)=O(n) 次排序调用。整体排序需要O(n)吗？这是否为函数提供了 O(n) 的 运行 时间？

Answer 1

是的，您的函数只需要 O(n)。不过请记住，它 不是 对给定集合进行排序。只有子集。因此，对于一组 n 值的 (comparison-based) 排序，n log n 下限没有冲突，因为您没有这样做。