javascript - JavaScript 数组的大 O

Question

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) prepending。如果使用动态扩展数组，O(log n) 将是这两种情况的平均情况。

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

附言

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

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)，因为您必须更新所有受影响的值。