Object.entries() 时间复杂度

Question

有谁知道 Javascript 中 Object.entries() 的复杂度？基于 this question 我猜想也许 O(n) 如果它是通过获取键和值作为数组然后将它们压缩在一起来实现的？

Answer 1

（此处为 V8 开发人员。）

简短回答：是的，在大多数情况下 Object.entries() 的复杂度是 O(n)。

对于大型对象（数千个属性），它是 O(n log n)。那是因为我们将大对象（以及某些“复杂”的小对象）的属性存储在字典中，而从该字典中检索所有键的复杂度为 O(n)，Object.entries() 被指定为 return 条目属性创建顺序，所以我们必须对它们进行排序，这是一个 O(n log n) 操作。
（Object.keys() 也是如此；您链接的 question/answer 在这方面是不正确的。）

此外，请记住，由于必须为每个条目分配一个数组，因此 Object.entries() 在用于大型对象时会留下大量垃圾。（但这并没有改变它的复杂性 class。）

还有一个可能更相关的问题：检索属性的值可能意味着调用 getter，而 getter 确实可以做任何事情，在这种情况下所有的赌注都关闭了。它甚至可能根本不会终止：

var o = {};
Object.defineProperty(o, "there's nothing O(n) about this",
                      {get: () => { while (true); }, enumerable: true});
console.log(Object.entries(o));

Object.entries() 时间复杂度

Object.entries() time complexity

javascript

arrays

v8

time-complexity