JavaScript 数组的 Big O

JavaScript 中的数组很容易通过添加和删除项目来修改。它在某种程度上掩盖了这样一个事实：大多数语言数组都是固定大小的，并且需要复杂的操作来调整大小。 JavaScript 似乎可以很容易地编写出性能不佳的数组代码。这就引出了一个问题：

在数组性能方面，我可以从 JavaScript 实现中获得什么性能（就大 O 时间复杂度而言）？

我假设所有合理的 JavaScript 实现最多有以下几个大 O。

• 访问 - O(1)
• 追加 - O(n)
• 前置 - O(n)
• 插入 - O(n)
• 删除 - O(n)
• 交换 - O(1)

JavaScript 允许您使用以下方法将数组预填充到特定大小new Array(length)句法。 （额外问题：以这种方式创建数组是 O(1) 还是 O(n)）这更像是传统数组，如果用作预先确定大小的数组，则可以允许 O(1) 追加。如果添加循环缓冲区逻辑，则可以实现 O(1) 前置。如果使用动态扩展数组，则 O(log n) 将是这两种情况的平均情况。

我可以期望某些事情的表现比我在这里的假设更好吗？我不希望任何规范中概述任何内容，但实际上，所有主要实现都可能在幕后使用优化的数组。是否有动态扩展数组或其他一些性能提升算法在起作用？

P.S.

我想知道这一点的原因是我正在研究一些排序算法，其中大多数在描述其整体大 O 时似乎假设附加和删除是 O(1) 操作。

_{NOTE: While this answer was correct in 2012, engines use very different internal representations for both objects and arrays today. This answer may or may not be true.}

与大多数使用数组实现数组的语言相反，在 Javascript 中数组是对象，值存储在哈希表中，就像常规对象值一样。像这样：

• 访问 - O(1)
• 追加 - 摊销 O(1)（有时需要调整哈希表的大小；通常只需要插入）
• 前置 - O(n) 通过unshift，因为它需要重新分配所有索引
• 插入 - 如果值不存在，则摊销 O(1)。 O(n) 如果你想移动现有的值（例如，使用splice).
• 删除 - 分摊 O(1) 来删除值，O(n) 如果您想通过以下方式重新分配索引splice.
• 交换 - O(1)

一般来说，设置或取消设置字典中的任何键都会摊销 O(1)，对于数组也是如此，无论索引是什么。任何需要对现有值重新编号的操作都是 O(n)，因为您必须更新所有受影响的值。