寻找数组中k个最小元素的时间复杂度：三种方法对比及疑问

三种实现思路 #

• 排序截取法：直接对整个数组做全量排序，然后取前k个元素。时间复杂度为O(nlog(n))，代码实现最简洁，但性能是三者里最差的——不管k的大小，都要为全量排序付出成本。
• 最小堆法：先将整个数组以O(n)时间堆化为最小堆，之后循环k次提取堆顶的最小元素（每次提取后堆的调整操作耗时O(log(n))），总时间复杂度为O(n + klog(n))。
• 固定容量最大堆法：维护一个大小严格为k的最大堆，遍历数组中的每个元素：如果堆还没满就直接加入；如果堆已满且当前元素比堆顶（堆内最大的元素）小，就弹出堆顶再把当前元素加进去。每次堆调整的时间是O(log(k))，总时间复杂度为O(nlog(k))。

最小堆与固定容量最大堆的性能对比 #

二者的优劣完全由k和n的相对大小决定：

1. 当k远小于n时（比如k是n的千分之一甚至更小）：
   最小堆法的总开销更接近O(n)，因为klog(n)的附加成本远小于n；而固定容量最大堆法的O(nlog(k))，即使log(k)很小，乘以n后的总开销会超过最小堆法的基础O(n)成本。不过要注意，固定容量最大堆的空间开销只有O(k)，远小于最小堆法的O(n)，如果内存资源紧张，它仍是更合适的选择。
2. 当k接近n时（比如k等于n/2）：
   最小堆法里的klog(n)项会接近甚至超过n，总开销升级为O(nlog(n))；而固定容量最大堆法的log(k)增长速度远慢于log(n)，总开销虽然也是O(nlog(n))级别，但实际运行的常数项更小，效率更高。
3. 中间区间：当k处于上述两种情况之间时，两者的性能差距不大，具体表现取决于堆实现的细节（比如编程语言内置堆操作的常数因子）。

内容的提问来源于stack exchange，提问作者Rishav Raj