JavaScript数组的时间复杂度
JavaScript数组的时间复杂度
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)。
对于某些方面，我可以期望比我在这里假设的性能更好吗？我不指望任何规范中有明确说明，但在实践中，所有主要实现可能都在幕后使用了优化的数组。是否存在动态扩展数组或其他性能提升算法？
附言：
我之所以想知道这个问题，是因为我正在研究一些排序算法，其中大多数算法在描述它们的整体大O时假设追加和删除是O(1)的操作。
大多数编程语言中，数组的操作时间复杂度都有明确的保证。但是，在JavaScript中，并没有对任何数组操作的时间复杂度做出具体保证。数组的性能取决于引擎选择的底层数据结构。引擎可能还会有不同的表示方式，并根据某些启发式算法进行切换。初始数组大小可能或可能不是这样的启发式算法。
例如，V8引擎（截至今天）同时使用哈希表和数组列表来表示数组。它还有多种不同的对象表示方式，因此无法直接比较数组和对象。因此，数组访问的时间复杂度总是优于O(n)，甚至可能和C++中的数组访问一样快。添加操作的时间复杂度是O(1)，除非达到了数据结构的大小限制，需要进行扩容（时间复杂度为O(n)）。而在数组的开头添加元素的性能较差。如果使用delete array[index]这样的方式进行删除操作（不建议这样做！），时间复杂度可能更高，因为这可能会强制引擎更改数组的表示方式。
为了获得最佳性能，应该将数组用于数值型数据结构，这正是数组的设计目的。引擎会针对这种情况进行优化。避免使用稀疏数组（如果必须使用，性能会较差）。避免使用具有混合数据类型的数组（因为这会使内部表示更复杂）。
如果您真的想要针对特定的引擎（和版本）进行优化，请查看其源代码以获取确切答案。
等一下，我们可以创建具有混合数据类型的数组吗？JavaScript太酷了！
确实可以，但在99%的情况下，您不需要这个功能。
威尔姆斯，请您详细解释一下unless you reach the size of the datastructure and it has to be scaled这部分的含义？在JavaScript中，我们通常不会在创建数组时设置数组长度，这是否意味着对于通过常规方式创建的任何数组（例如let a = [1,2,3]），添加元素都需要进行数据结构的扩容呢？
我认为不需要，在这种情况下，引擎可能会直接分配一个具有更大大小的数组列表。
JavaScript中数组的Big O表示法问题的出现原因是因为JavaScript中的数组实际上是对象，值存储在哈希表中，而不是像大多数其他语言一样使用数组。所以：
- 访问 - O(1)
- 添加 - 平摊 O(1)（有时需要调整哈希表的大小；通常只需要插入）
- 前置 - O(n) 通过unshift，因为它需要重新分配所有的索引
- 插入 - 平摊 O(1)（如果值不存在）。如果要移动现有的值，则为O(n)（例如，使用splice）。
- 删除 - 平摊 O(1) 删除一个值，如果要通过splice重新分配索引，则为O(n)。
- 交换 - O(1)
一般来说，设置或取消字典中的任何键都是平摊 O(1)，对于数组也是如此，无论索引是什么。任何需要重新编号现有值的操作都是O(n)，因为您必须更新所有受影响的值。
JavaScript没有重新分配数组索引的'prepend'，'insert'或'delete'操作。它确实有一个可以执行这些操作的'splice'操作，并且（显然）是O(n)。
关于length，请参见这里。
这个答案不再正确。现代引擎不会将数组（或具有索引整数键的对象）存储为哈希表（但像C语言中的数组）。这个问题的一个经典基准测试可以说明这一点。
据我所知，这不会影响复杂性或行为，只会影响常数因子（超出了问题的范围）。
这些值只是哈希表的值，您可以在维基百科或其他地方查找大O分析。
这是否由标准定义，还是只是JavaScript引擎中的常见实现？V8引擎是怎样的？
如果你能详细说明一下它们是如何存储的就好了。或者提供一些来源。
我还是有点困惑。new Array(100000)比new Array(10)慢吗？
可以说它的行为类似于一个高效的栈/先进先出（FIFO），但不是一个队列/先进后出（FILO）吗？
那么现在的答案是什么呢？
摊销是什么意思？这是否意味着通过.pop进行的删除操作是O(1)？