JavaScript中unshift()和push()的时间复杂度

我知道Javascript中的unshift()和push()方法有什么区别,但是我想知道时间复杂度有什么区别?

我想push()方法是O(1),因为你只是添加一个项目到数组的末尾,但我不确定unshift()方法,因为,我想你必须“移动”所有其他现有的元素转发,我想这是O(log n)或O(n)?

就我所知,JavaScript语言规范并没有强制这些函数的时间复杂性。

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

但是如果你需要保证这样的时间限制,你将不得不自己推出,就像这样:

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

push()更快。

 js>function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)} js>foo() 2190 js>function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)} js>bar() 10 

恕我直言,这取决于JavaScript引擎…如果它将使用链表,不换档应该是相当便宜… … –

使用快速移位和推送来实现数组的一种方法是简单地将数据放入C级数组中。 这就是Perl的做法,IIRC。

另一种方法是使用两个独立的C级数组,这样push就会追加到其中一个数组中,而不会移位到另一个数组中。 我知道这个方法比前一个方法没有什么实际的好处。

无论如何实现,当内部C级arrays具有足够的空闲内存时,推或不移将花费O(1)时间,否则当必须重新分配时,至less需要O(N)时间来复制旧数据到新的内存块。