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)时间来复制旧数据到新的内存块。