Javascript中unshift（）与push（）的时间复杂度 [英] time complexity of unshift() vs. push() in Javascript

问题描述

我知道Javascript中unshift（）和push（）方法之间的区别是什么，但我想知道时间复杂度有什么不同？

I know what is the difference between unshift() and push() methods in Javascript, but I'm wondering what is the difference in time complexity?

I假设push（）方法是O（1），因为你只是将一个项添加到数组的末尾，但我不确定unshift（）方法，因为，我想你必须移动所有其他现有的元素转发，我想是O（log n）或O（n）？

I suppose for push() method is O(1) because you're just adding an item to the end of array, but I'm not sure for unshift() method, because, I suppose you must "move" all the other existing elements forward and I suppose that is O(log n) or O(n)?

推荐答案

JavaScript语言规范没有强制要求据我所知，这些函数的时间复杂度。

The JavaScript language spec does not mandate the time complexity of these functions, as far as I know.

当然可以用O实现类似数组的数据结构（O（1）随机访问） （1） push 和 unshift 操作。 C ++ std :: deque 就是一个例子。因此，使用C ++ deques在内部表示Javascript数组的Javascript实现将具有O（1） push 和 unshift 操作。

It is certainly possible to implement an array-like data structure (O(1) random access) with O(1) push and unshift operations. The C++ std::deque is an example. A Javascript implementation that used C++ deques to represent Javascript arrays internally would therefore have O(1) push and unshift operations.

但是如果你需要保证这样的时间限制，你必须自己动手，如下所示：

But if you need to guarantee such time bounds, you will have to roll your own, like this:

http://code.stephenmorley.org/javascript/queues/

这篇关于Javascript中unshift（）与push（）的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！