javascript - Google Chrome 中 array.splice() 的时间复杂度是多少？

Question

如果我像这样使用 splice() 从数组中删除一个元素:

arr.splice(i, 1);

在最坏的情况下，这会是 O(n) 吗，因为它移动了 i 之后的所有元素？或者它是常数时间，下面有一些链表魔法？

Answer 1

最坏的情况应该是O(n)(将所有n-1 元素复制到新数组)。

对于单个删除，链表的复杂度为 O(1)。

对于那些感兴趣的人，我制作了这个懒惰制作的 benchmark . (Please don't run on Windows XP/Vista)。 正如您从中看到的那样，它看起来相当稳定(即 O(1))，所以谁知道他们在幕后做了什么来让这个速度变得如此之快。请注意，无论如何，实际的 splice 都非常快。

重新运行 extended benchmark直接在建议 O(n) 的 V8 shell 中。请注意，您需要巨大的数组大小才能获得可能会影响您的代码的运行时。这应该是意料之中的，就像您查看它使用 memmove 来创建新数组的 V8 代码一样。