数组中前 k 个频繁元素的时间和 Space 复杂度
Time and Space Complexity of top k frequent elements in an array
关于给定问题的时间和 space 复杂性存在一些小混淆：
给定一个大小为 N 的数组，return 一个包含前 K 个频繁元素的列表。
基于最受欢迎的解决方案：
- 使用大小为 K 的 HashMap，每个条目的计数作为值。
- 遍历上面生成的HashMap，构建一个大小为K的MaxHeap
- 将 MaxHeap 中的元素弹出到列表中，然后 return 列表。
K 是输入中唯一元素的数量。
space 时间复杂度为：O(K) 和 O(K*log(K)
现在混乱从这里开始。我们知道在上述分析中我们正在处理最坏情况下的复杂性。因此，当数组中的所有元素都是唯一的时，K 可以取的最差值是 N。
因此K <= N。从而O(K)表示为O(N) ??
因此，上述问题的space和时间复杂度不应该是O(N)和O(N*log(N))吗？
我知道这是一个技术问题，但它已经困扰了我一段时间。请指教。
是的，你是对的，因为 K<N，hashmap 部分的时间复杂度应该是 O(N)。
但是堆中只有 K 个元素，并且具有 O(Klog(K)) 的时间复杂度，如果渐近地考虑，它远大于 O(N) 的线性复杂度，因此导致最终时间复杂度 O(Klog(K)).
关于给定问题的时间和 space 复杂性存在一些小混淆：
给定一个大小为 N 的数组，return 一个包含前 K 个频繁元素的列表。
基于最受欢迎的解决方案：
- 使用大小为 K 的 HashMap，每个条目的计数作为值。
- 遍历上面生成的HashMap，构建一个大小为K的MaxHeap
- 将 MaxHeap 中的元素弹出到列表中，然后 return 列表。
K 是输入中唯一元素的数量。
space 时间复杂度为：O(K) 和 O(K*log(K)
现在混乱从这里开始。我们知道在上述分析中我们正在处理最坏情况下的复杂性。因此，当数组中的所有元素都是唯一的时，K 可以取的最差值是 N。
因此K <= N。从而O(K)表示为O(N) ??
因此，上述问题的space和时间复杂度不应该是O(N)和O(N*log(N))吗？
我知道这是一个技术问题，但它已经困扰了我一段时间。请指教。
是的，你是对的，因为 K<N，hashmap 部分的时间复杂度应该是 O(N)。
但是堆中只有 K 个元素，并且具有 O(Klog(K)) 的时间复杂度，如果渐近地考虑，它远大于 O(N) 的线性复杂度，因此导致最终时间复杂度 O(Klog(K)).