如果我使用 splice() 从数组中删除一个元素，如下所示：
arr.splice(i, 1);
这会是O(n)在最坏的情况下，因为它会移动 i 之后的所有元素？或者它是常数时间，下面有一些链表魔法？
最坏的情况下should be O(n)（复制所有n-1元素到新数组）。
链表将是O(1)对于单个删除。
对于那些感兴趣的人，我做了这个懒惰的制作基准 http://jsfiddle.net/eXgkT/1/. (请不要在 Windows XP/Vista 上运行 http://ejohn.org/blog/accuracy-of-javascript-time/）。 正如你所看到的，它看起来相当稳定（即O(1)），所以谁知道他们在幕后做了什么才能让这一切变得如此疯狂。请注意，无论如何，实际splice非常快。
重新运行扩展基准 http://jsfiddle.net/eXgkT/2/直接在 V8 shell 中提示O(n)。但请注意，您需要巨大的数组大小才能获得可能影响代码的运行时。这应该是预料之中的，就像您查看它使用的 V8 代码一样memmove创建新数组。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
