unshift()和push()方法的区别在于它们是从数组的不同位置添加元素的，但我想知道它们的时间复杂度有什么不同？push()方法的时间复杂度是O(1)，因为你只是将一个元素添加到数组的末尾，但我不确定unshift()方法的时间复杂度，因为我认为您必须将所有现有元素向前“移动”，我认为这是O(log n)或O(n)？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());以上内容没有考虑数组的顺序。如果您想要正确比较它们，您必须颠倒被推入的数组。然而，在 Chrome 浏览器中，使用 push 然后 reverse 仍然比这个代码片段中的其他方法快约 10ms：
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}`);push和shift比使用unshift和pop更快。 - douggardunshift需要8毫秒，而push只需要3毫秒。 - acrogenesis据我所知，JavaScript语言规范并没有规定这些函数的时间复杂度。
当然，可以用 O(1) 随机访问来实现类似数组的数据结构，并且具有 O(1) 的 push 和 unshift 操作。C++的 std::deque 就是一个例子。如果Javascript实现使用C++ deques来内部表示Javascript数组，那么它将具有O(1)的push和unshift操作。
但是，如果您需要保证此类时间复杂度，您必须自己编写代码，例如：
对于对v8实现感到好奇的人，这里是源代码。因为unshift接受任意数量的参数，所以数组会自动移位以容纳所有参数。
UnshiftImpl最终使用AddArguments和start_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);
}
}
元素种类的概念，具体取决于数组包含的内容。这也会影响性能。unshift需要在数组中分配更多的空间，在一般情况下，你可以假设它是O(N)（将根据元素数量线性扩展），但如果我错了，请纠正我。是的，你说得对。默认情况下，push()的复杂度为O（1），而unshift()的复杂度为O（n）。因为unshift()必须增加数组中已经存在的所有元素。但是，push()必须在数组末尾插入一个元素，因此不需要更改任何数组元素的索引。但是，由于动态分配内存，push()的复杂度也可以称为O（n）。在JavaScript中，如果您创建一个没有指定大小的新数组，则会创建一个默认值的数组。直到填充了默认大小，推动操作需要O（1）复杂度。但是，如果默认大小已满，则编译器必须创建一个新的连续内存块，其大小是默认内存的两倍，并将已经存在的元素复制到新分配的内存中。因此，将元素从一个连续的内存块移动到另一个连续的内存块需要O（n）时间。
如果您知道要放入数组中的元素数量，则可以避免插入元素时出现O（n）。
let array = new Array(size).fill(0)for (let i = 0; i < size; i++) {
array[i] = i
}
因此，我们改变了元素在其位置上的索引，而不是使用push（）。这比创建带有默认值并将元素推入其中的数组更加内存高效和简单。由于仅使用所需的内存，因此不会浪费任何额外的内存。
.push 的 O(n) 复杂度的说法是错误的。
它实际上是摊销的 O(1)。
请熟悉摊销算法复杂度 https://dev59.com/OXVC5IYBdhLWcg3wtzyt#249695 - deorst在我看来，这取决于JavaScript引擎的使用情况...如果它使用了链表，unshift操作应该是相当便宜的...
push的时间复杂度：O(n)unshift的时间复杂度：O(m + n)其中：
m是现有数组的长度。n是要添加的元素数量。
pop的时间复杂度：O(1)shift的时间复杂度：O(n)，其中n为数组的长度这是JavaScript中的一个数组数据结构实现，希望这能让事情更清晰明了。
class XArray {
constructor() {
Object.defineProperties(this, {
length: {
writable: true,
enumerable: false,
configurable: false,
value: 0,
},
});
/** Configure the output of the Array object to return only values */
const runtimeConsole = console;
console = {
...console,
log: function (data) {
if (XArray.isArray(data)) {
runtimeConsole.log(Object.values(data));
} else runtimeConsole.log(data);
},
};
}
/**
* Adds element(s) to the end of the array
*
* Time Complexity: O(n)
* @param {...any} elements
*/
push(...elements) {
for (const element of elements) {
this[this.length] = element;
this.length++;
}
return this.length;
}
pop() {
const element = this[this.length - 1];
delete this[this.length - 1];
this.length--;
return element;
}
/**
* Adds elements to the beginning of the array
*
* Time Complexity: O(m + n)
*
* @param {...any} elements
*/
unshift(...elements) {
for (let i = this.length - 1; i >= 0; i--) {
this[i + elements.length] = this[i];
}
for (const index in elements) {
this[index] = elements[index];
this.length++;
}
this.length;
}
shift() {
const element = this[0];
this.length--;
for (let i = 0; i < this.length; i++) {
this[i] = this[i + 1];
}
delete this[this.length];
return element;
}
static isArray(array) {
return array instanceof XArray;
}
}
Unshift的时间复杂度为O(n)。如果我的数组是["cat", "dog"]，并且我在第一个位置上unshift "moose"，那么数组中剩余的所有元素都必须“移动”。也就是说，每个元素在将"moose"添加到第一个位置后，其索引都会增加。
Push的时间复杂度为O(1)。如果我的数组是["cat", "dog"]，并且我将"moose"推入数组的末尾，那么所有元素都可以保持原位。
unshift 比 push 慢，因为它还需要在添加第一个元素后将所有元素向左移一位。所以对于 unshift，时间复杂度为 o(n)，而 push 的时间复杂度为 o(1)。
unshift可以接近常数时间，但我不得不想知道是否值得为了复杂化正常的数组访问而这样做。我个人认为我从来没有写过一个unshift的调用。 - Pointy