arrays - 数组中前k个频繁元素的时空复杂度

Question

关于给定问题的时间和空间复杂度有一个小的混淆：

给定一个大小为N的数组，返回前K个频繁元素的列表。

基于最流行的解决方案：

1. 使用大小为K的 HashMap，并将每个条目的计数作为值。
2. 通过遍历上面生成的 HashMap构建一个大小为K的 MaxHeap 。
3. 将 MaxHeap 中的元素弹出到一个列表中并返回该列表。

K 是输入中唯一元素的数量。

空间和时间复杂度为：O(K) 和 O(K*log(K)

现在混乱从这里开始。我们知道在上述分析中我们正在处理最坏情况的复杂性。因此，当数组中的所有元素都是唯一的时，K 可以取的最差值是 N。

因此 K <= N。因此 O(K) 表示为 O(N) ??

因此，对于上述问题，空间和时间复杂度不应该是 O(N) 和 O(N*log(N)) 吗？

我知道这是一个技术问题，但它一直困扰着我一段时间。请指教。

Answer 1

是的，你是对的，因为K<Nhashmap 部分的时间复杂度应该是O(N)。

但是堆中只有 K 个元素，并且O(Klog(K))如果渐近考虑，其时间复杂度远大于线性复杂度O(N)，因此最终的时间复杂度为O(Klog(K)).