JavaScript数组的大O表示法

Question

JavaScript中的数组很容易通过添加和删除项进行修改。这在某种程度上掩盖了大多数语言中数组是固定大小，并需要复杂操作来调整大小的事实。似乎JavaScript使编写性能较差的数组代码变得容易。这引出了一个问题：
关于数组性能，我可以从JavaScript实现中期望什么样的性能（大O时间复杂度）？
我假设所有合理的JavaScript实现最多具有以下Big 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(1)操作，当描述它们的总体Big O时。

- Kendall Frey

---

在现代JavaScript实现中，带有大小参数的Array构造函数几乎是无用的。它在单个参数形式下几乎什么也不做（它设置.length但只有这一个作用）。数组与普通对象实例并没有太大区别。 - Pointy

设置 length 属性和预先分配空间是两个完全不同的操作。 - Pointy

@Pointy：当我期望在new Array(10)上设置array[5]是O(1)时，我是否期望过高了？ - Kendall Frey

虽然ECMAScript没有定义如何实现Array对象（它只定义了一些语义规则），但不同的实现很可能会针对预期情况进行优化（例如，对于小于某个n大小的数组具有“真实数组”支持）。我对实现不是很熟悉，但如果这种优化在某个地方没有被执行，我会感到非常惊讶... - user166390

“最佳答案”可能是编写一些JSPerf测试用例来测试不同的 n / 访问模式，并查看它们的结果。;-) - user166390

Answer 1

_{注意：尽管此答案在2012年是正确的，但今天引擎对对象和数组使用非常不同的内部表示。此答案可能正确，也可能不正确。}

与大多数语言实现数组的方式相反，在Javascript中，数组是对象，值存储在哈希表中，就像普通对象值一样。因此：

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

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

- Nick Johnson

---

要在任意索引处插入和删除元素，都需要将所有索引进行移动。因此，在这种情况下，prepend、insertion 和 deletion 的时间复杂度都应该是 O(n)。 - nhahtdh

值得一提的是，这个答案不再正确。现代引擎不会将数组（或带有索引整数键的对象）存储为哈希表（而是像 C 语言中的数组一样），除非它们是稀疏的。为了让你开始学习，这里有一个“经典”的基准测试可以说明这一点。 - Benjamin Gruenbaum

这是由标准定义的还是JS引擎中常见的实现方式？V8引擎又如何呢？ - Albert

@BenjaminGruenbaum 如果您能详细阐述它们是如何存储的就太好了，或者提供一些来源。 - Ced

摊销是什么意思？这是否意味着通过.pop进行删除的时间复杂度为O(1)？ - Noitidart

Answer 2

保证

对于任何数组操作，都没有指定的时间复杂度保证。数组的表现取决于引擎选择的底层数据结构。引擎也可能有不同的表示形式，并根据某些启发式算法在它们之间切换。最初的数组大小可能是这种启发式算法。

现实

例如，V8（截至今日）使用哈希表和数组列表来表示数组。它还有各种不同的对象表示形式，因此无法将数组和对象进行比较。因此，数组访问始终优于O(n)，甚至可能与C++的数组访问一样快。添加是O(1)，除非达到数据结构的大小并且必须进行扩展（这是O(n)）。预置更糟。如果您执行delete array[index]之类的操作（不要这样做！），删除甚至可能更糟，因为那可能会强制引擎更改其表示。

建议

使用数组来处理数值数据结构。这就是它们的设计目的，也是引擎对它们进行优化的原因。避免使用稀疏数组（如果必须使用，则性能会更差）。避免使用混合数据类型的数组（因为这会使内部表示更加复杂）。

如果您真的想针对某个引擎（和版本）进行优化，请查看其源代码以获取绝对答案。

- Jonas Wilms

---

等一下，我们可以使用混合数据类型的数组吗？Javascript 真是太酷了！ - Anurag Baundwal

@Anurag 没错，但在99%的情况下，您不需要此功能。 - Desiigner

@Jonas-Wilms，您能否详细说明“除非您达到数据结构的大小并且必须进行扩展”这部分内容？在JS中，我们通常不会在数组创建时设置数组长度，这是否意味着对于以常规方式创建的任何数组（例如let a = [1,2,3]），追加操作都需要进行数据结构扩展？ - grreeenn

@grreeenn 我猜不会，引擎可能会直接分配一个更大尺寸的数组列表。 - Jonas Wilms