Array函数的JavaScript运行时复杂性

Question

由JS标准共同定义的运行复杂Array的功能,如push,pop,shift,slice或splice？ESP.我有兴趣在随机位置删除和插入条目.如果未定义复杂性,我可以期待什么,例如在V8中？

(这个问题的灵感来自于此.此外,这个贴在这里的基准也让我很好奇,但也许这是一些无关的现象.)

(一个非常相关的问题在这里.但是,对接受的答案的评论之一说现在是错误的.另外,接受的答案没有任何参考标准真正定义它的方式.).

Answer 1

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.

Answer 2

用非常简单的话来说

推 -> O(1)

弹出 -> O(1)

移位 -> O(N)

切片 -> O(N)

拼接 -> O(N)

这是关于 JavaScript 中数组时间复杂度的完整解释。