JavaScript中unshift（）和push（）的时间复杂度
我知道Javascript中的unshift（）和push（）方法有什么区别，但是我想知道时间复杂度有什么区别？
我想push（）方法是O（1），因为你只是添加一个项目到数组的末尾，但我不确定unshift（）方法，因为，我想你必须“移动”所有其他现有的元素转发，我想这是O（log n）或O（n）？
就我所知，JavaScript语言规范并没有强制这些函数的时间复杂性。
用O（1） push和unshift操作实现类似数组的数据结构（O（1）随机访问）当然是可能的。 C ++ std::deque就是一个例子。 使用C ++ deques在内部表示Javascript数组的Javascript实现因此具有O（1） push和不unshift操作。
但是如果你需要保证这样的时间限制，你将不得不自己推出，就像这样：
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）时间来复制旧数据到新的内存块。
