javascript - 数组方法的复杂性

Question

在团队项目中，我们需要删除数组的第一个元素，因此我调用了Array.prototype.shift()。 .现在一个人看到了Why is pop faster than shift? , 因此建议首先反转数组，弹出，然后再次反转，用 Array.prototype.pop()和 Array.prototype.reverse() .

直觉上这会更慢(？)，因为我的方法需要 O(n) 我认为，而另一个需要 O(n)，再加上 O(n)。当然，在渐近符号中，这将是相同的。但是请注意我使用的动词，思考!

当然我可以写一些，使用jsPerf和基准测试，但这需要时间(与通过时间复杂度符号决定相比(例如 O(n³) 与 O(n) 算法)。

但是，在使用我的意见时说服某人比向他指出标准(如果它涉及复杂性)要困难得多。

那么如何找到这些方法的时间复杂度呢？

例如在 C++ 中 std::reverse()明确指出:

Complexity

Linear in half the distance between first and last: Swaps elements.

Answer 1

how to find the Time Complexity of these methods?

您无法在标准中找到它们。

ECMAScript 是脚本语言的标准。 JavaScript 就是这样一种语言。

ECMA 规范没有指定边界复杂度。只要与标准兼容，每个 JavaScript 引擎都可以自由实现自己的功能。

因此，您必须使用 jsPerf 进行基准测试，甚至可以查看特定 JavaScript 引擎的源代码，如果您愿意的话。

或者，如 robertklep 的评论所述:

“标准没有规定这些方法应该如何实现。此外，JS 是一种解释型语言，因此 JIT 和 GC 之类的东西可能会开始发挥作用，具体取决于数组大小和调用代码的频率。在其他换言之:基准测试可能是您了解不同 JS 引擎性能的唯一选择。”

此声明有进一步的证据([0]、 [1]、 [2])。