无序数组取第k小元素的有序Map实现的时间空间复杂度是多少

首先要说明：你的这个实现能正确运行的前提是依赖ES6及以上版本的JS规范——普通对象的数字类型键会按照数值升序的顺序被Object.entries遍历返回，脱离这个规范约束的话，代码逻辑本身是不成立的。

时间复杂度 #

• 第一步orderedMapFrequency函数需要完整遍历长度为n的输入数组统计每个元素的出现频次，这一步的开销固定是O(n)，没有提前终止的可能
• 第二步遍历频次统计对象，遍历次数等于数组中不同元素的个数m：最优情况下第一个元素的累计频次就满足k的要求，开销为O(1)；最坏情况下所有元素都不重复，需要遍历n次，开销为O(n)
• 整体时间复杂度由最高阶的开销项决定，无论最优还是最坏场景，整体时间复杂度都是O(n)，你猜测的O(logn)是不成立的，因为统计频次必须遍历所有元素，时间开销不可能低于线性级别。

空间复杂度 #

• 你实现的额外空间仅用于存储频次统计对象，占用空间大小等于数组中不同元素的个数m：最坏场景下所有元素都不重复，m等于n，因此最坏空间复杂度为O(n)；如果数组存在大量重复元素，实际的空间开销会比O(n)更小。

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