javascript - JavaScript array.length 的时间复杂度

Question

在 JavaScript 中调用 array.length 的时间复杂度是多少？我认为它会保持不变，因为似乎属性是在所有数组上自动设置的，而您只是在查找它？

Answer 1

I think it would be constant since it seems that property is set automatically on all arrays and you're just looking it up?

对。它是一个被存储(而不是计算)并根据需要自动更新的属性。规范对此有明确说明 here和 here其中包括其他地方。

理论上，JavaScript 引擎可以自由计算 length在访问时就好像它是一个访问器属性，只要您无法分辨(这意味着它实际上不可能是一个访问器属性，因为您可以在代码中检测到它)，但考虑到 length被重复使用很多(for (let n = 0; n < array.length; ++n)浮现在脑海中)，我认为我们可以假设所有广泛使用的 JavaScript 引擎都会按照规范的规定执行操作，或者至少执行恒定时间访问的操作。

<小时/>

FWIW:请记住，理论上 JavaScript 的标准数组只是 objects with special behavior 。 理论上，JavaScript 对象是属性包。因此，理论上，如果对象被实现为某种名称->值 HashMap (在过去的糟糕日子里，它们曾经是这样的话)，那么在属性包中查找属性可能取决于有多少其他属性)。现代引擎优化对象(众所周知，Chrome 的 V8 动态创建动态类并编译它们)，但对这些对象的操作仍然可以改变属性查找性能。例如，添加属性可能会导致 V8 创建子类。删除属性(实际上使用 delete )可能会使 V8 放弃并退回到“字典模式”，这会大大降低对对象的属性访问。

换句话说:不同的引擎，甚至不同的对象，它可能会有所不同。但是，如果您纯粹将数组用作数组(不在其上存储其他非数组属性)，那么您很可能会获得恒定时间查找。