我知道 JavaScript 中的unshift()和push()方法有什么区别，但我想知道时间复杂度有什么区别？
我想push()方法是 O(1) 因为你只是在数组的末尾添加一个项目，但我不确定unshift()方法，因为，我想你必须向前“移动”所有其他现有元素，我想那是 O(log n) 还是 O(n)？
问问题
36843 次
6 回答
70
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
function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
console.log(foo())
function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
console.log(bar());更新
以上没有考虑数组的顺序。如果要正确比较它们，则必须反转推送的数组。10ms但是，对于我来说，使用以下代码段在 chrome 上推送然后反向仍然更快：
var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
a.unshift(1);
}
var end = (new Date)-start;
console.log(`Unshift time: ${end}`);
var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
a.push(1);
}
a.reverse();
var end = (new Date)-start;
console.log(`Push and reverse time: ${end}`);于 2014-10-14T21:26:33.667 回答
27
据我所知，JavaScript 语言规范并没有规定这些函数的时间复杂度。
push当然可以使用 O(1)和unshift操作来实现类似数组的数据结构（O(1) 随机访问） 。C++std::deque就是一个例子。因此，使用 C++ 双端队列在内部表示 Javascript 数组的 Javascript 实现将具有 O(1)push和unshift操作。
但是如果你需要保证这样的时间限制，你将不得不自己动手，像这样：
于 2012-09-03T15:40:58.520 回答
15
对于对 v8 实现感到好奇的人，这里是源代码。因为unshift接受任意数量的参数，所以数组将自行移动以容纳所有参数。
UnshiftImpl最终调用AddArgumentsastart_position将AT_START其踢到此else语句
// If the backing store has enough capacity and we add elements to the
// start we have to shift the existing objects.
Isolate* isolate = receiver->GetIsolate();
Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
length, 0, 0);
并将其带到MoveElements.
static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
Handle<FixedArrayBase> backing_store, int dst_index,
int src_index, int len, int hole_start,
int hole_end) {
Heap* heap = isolate->heap();
Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
heap->CanMoveObjectStart(*dst_elms)) {
// Update all the copies of this backing_store handle.
*dst_elms.location() =
BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
->ptr();
receiver->set_elements(*dst_elms);
// Adjust the hole offset as the array has been shrunk.
hole_end -= src_index;
DCHECK_LE(hole_start, backing_store->length());
DCHECK_LE(hole_end, backing_store->length());
} else if (len != 0) {
WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
}
if (hole_start != hole_end) {
dst_elms->FillWithHoles(hole_start, hole_end);
}
}
我还想指出，v8 有一个不同的概念，element kinds具体取决于数组包含的内容。这也会影响性能。
很难真正说出性能是什么，因为实际上它取决于传递的元素类型，数组中有多少个孔等。如果我再深入研究一下，也许我可以给出明确的答案，但总的来说我假设因为unshift需要在数组中分配更多空间，一般来说你可以假设它是 O(N) （将根据元素的数量线性缩放）但是如果我错了，请有人纠正我。
于 2018-12-04T03:41:30.423 回答
4
恕我直言，这取决于javascript引擎...如果它将使用链表，那么 unshift 应该很便宜...
于 2012-09-03T15:36:22.933 回答
4
实现具有快速 unshift 和 push 的数组的一种方法是简单地将数据放入 C 级数组的中间。这就是 perl 的做法，IIRC。
另一种方法是使用两个单独的 C 级数组，以便 push 附加到其中一个，而 unshift 附加到另一个。据我所知，与前一种方法相比，这种方法没有真正的好处。
不管它是如何实现的，当内部 C 级数组有足够的空闲内存时，push 或 unshift 将花费 O(1) 时间，否则，当必须进行重新分配时，复制旧数据至少需要 O(N) 时间到新的内存块。
于 2015-12-02T01:25:57.397 回答
3
是的你是对的。的默认复杂度push()为 O(1)，unshift()为 O(n)。因为unshift()必须增加数组中已经存在的所有元素。但是，push()必须在数组末尾插入一个元素，因此 Array 元素的索引不必更改。但，push()由于内存的动态分配，也可以说复杂度为 O(n)。在 javascript 中，当您创建一个新的 Array 而不指定所需的大小时，它将创建一个默认值的 Array。在填充默认大小之前，推送操作需要 O(1) 复杂度。但是，如果默认大小已满，编译器必须创建一个新的连续内存块，它是默认内存大小的两倍，并将已经存在的元素复制到新分配的内存中。因此，将元素从一个连续的内存块移动到另一个连续的内存块需要 O(n) 时间。
如果您知道要放入数组中的元素数量，则可以避免插入元素的 O(n)。
- 用所需的大小初始化数组，并用一个虚拟值填充它。
let array = new Array(size).fill(0) - 遍历您想要推送的元素并通过其索引更改值。
for (let i = 0; i < size; i++) {
array[i] = i
}
因此，push()我们没有更改元素在其位置的索引。与创建具有默认值的数组并将元素推送到其中相比，它的内存效率更高且复杂性更低。由于我们只使用了所需的内存量，因此不会浪费额外的内存。
于 2021-05-28T03:49:06.470 回答