JavaScript数组函数的运行时间复杂度

Question

JavaScript数组函数的运行时间复杂度

javascriptarraystime-complexity

93

JS标准中是否定义了常见Array函数（如push，pop，shift，slice或splice）的运行时复杂度？特别是我对在随机位置删除和插入条目很感兴趣。如果没有定义复杂度，我可以期待什么呢，例如在V8中？

（这个问题的灵感来自这里。此外，这个基准测试，发布于这里，也让我很好奇，但也许那是某些不相关的现象。）

（一个非常相关的问题在这里。但是，被接受的答案之一的评论说现在它是错误的。此外，被接受的答案没有任何参考文献表明标准确实是这样定义的。）

- Albert

4个回答

15

用简单易懂的话来说

push -> O(1)（常数时间复杂度）

pop -> O(1)（常数时间复杂度）

shift -> O(N)（线性时间复杂度）

slice -> O(N)（线性时间复杂度）

splice -> O(N)（线性时间复杂度）

这里有一个关于JavaScript数组时间复杂度的完整解释。

- Sarwar Sateer

1

没错，Array.prototype.splice 是一种通用的多功能工具，其复杂性取决于它所执行的操作。例如，它可以删除和/或添加最后一个元素（如 push 或 pop），那么复杂度将为 O(1)；如果它执行与 shift / unshift 相同的操作，则其复杂度将为 O(n)。此外，还有其他“中间”情况是可能的。 - Roman Karagodin

1

是的，我们可以说，在最坏的情况下，它仍然是O(n)。 - Sarwar Sateer

那篇文章提出了很多假设，但没有引用标准（标准也没有指定复杂性）或任何特定的引擎。仅仅因为以那种方式实现会很聪明，并不意味着任何特定的实现都必须这样做。 - General Grievance

3

顺便提一下，使用环形缓冲区（即CircularQueue / CircularBuffer）数据结构可以实现shift / unshift、push / pop方法的O(1)实现。只有在不需要扩展循环缓冲区时，最坏情况下的时间复杂度是O(1)。是否有人真正测量了这些操作的性能？毕竟知道总比猜测好...

- Lu4

1

是的，我几个月前在jsperf上试过了 - shift和unshift确实比O（1）更接近O（n），并且在n很大时速度要慢得多。为了避免使用shift和unshift，我制作了这个队列实现 https://gist.github.com/tbjgolden/142f2e0b2c1670812959e3588c4fa8a2 - tbjgolden

1

@TomGolden - 抱歉，不想太突兀，但是那个实现需要几个警告。它从不让任何东西离开。它不仅会累积未使用的数组槽，还会保留对这些未使用的数组槽中对象的引用。如果将大型对象推入该队列，则会永久保留它们，导致内存使用量在O(n)上升，如果在使用队列期间添加的总项目大小。至少，请在使用dequeue删除它们后将数组槽设置为未定义。 - huntharo

-13

如果取的切片数量是未知的，那么切片就是线性的。但如果切片数量是固定的，那么切片就是常数，而不是线性的。

- Seth Koch

13

同样的道理也适用于任何算法。如果数组中的元素数量是恒定的，那么你可以说对该数组进行排序是一个常数时间操作。出于明显的原因，这并不是非常有用的信息，因此它被投下了许多反对票。 - Michael Dorst

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chuckj · Accepted Answer

ECMA规范没有指定边界复杂度，但可以从规范的算法中推导出一个。

push是O(1)，但在实践中，它会在引擎定义的边界处遇到O(N)的复制成本，因为需要重新分配插槽数组。这些边界通常是对数的。

pop是O(1)，与push类似，但O(N)的复制很少遇到，因为它经常被折叠到垃圾收集中（例如，复制收集器只能复制数组的使用部分）。

shift最坏情况下是O(N)，但在特殊情况下，可以实现为O(1)，但会降低索引速度，所以具体情况可能有所不同。

slice是O(N)，其中N是end - start。在不显著减慢两个数组的写入的情况下，这里没有太多优化机会。

splice最坏情况下是O(N)。有一些数组存储技术可以将N除以一个常数，但它们会显著降低索引速度。如果引擎使用这种技术，当它在访问模式变化时切换存储技术时，您可能会注意到异常缓慢的操作。

你没有提到的一个是sort。平均情况下，它是O(N log N)。然而，根据引擎选择的算法，在某些情况下，你可能会得到O(N^2)。例如，如果引擎使用QuickSort（即使晚期开启InsertionSort），它具有众所周知的N^2情况。这可能是应用程序DoS的一个来源。如果这是一个问题，请限制您要排序的数组大小（也许合并子数组），或者停止使用HeapSort。