JavaScript数组的大O
JavaScript中的数组非常容易通过添加和删除项目进行修改。 它有点掩盖了大多数语言数组是固定大小的事实，并且需要复杂的操作来resize。 JavaScript似乎很容易编写性能不佳的数组代码。 这导致了一个问题：
在数组性能方面，我可以从JavaScript实现中期望什么样的性能（就大O时间复杂度而言）？
我认为所有合理的JavaScript实现至less有以下大O.
- 访问 – O（1）
- 附加 – O（n）
- 预先计划 – O（n）
- 插入 – O（n）
- 删除 – O（n）
- 交换 – O（1）
JavaScript允许使用new Array(length)语法将数组预先填充到特定的大小。 （奖金问题：以这种方式创build一个数组O（1）或O（n））这更像是一个常规的数组，如果用作预先大小的数组，可以允许O（1）追加。 如果添加了循环缓冲区逻辑，则可以实现O（1）预先计划。 如果使用dynamic扩展的数组，O（log n）将是这两者的平均情况。
我能期待比我的假设更好的performance吗？ 我不希望在任何规范中列出任何内容，但实际上可能是所有主要实现都在后台使用优化的数组。 是否有dynamic扩展数组或其他性能提升algorithm在工作？
PS
我想知道这个的原因是因为我正在研究一些sortingalgorithm，其中大部分似乎假定追加和删除O（1）操作时，描述他们的整体大O.
与大多数实现具有数组的数组的语言相比，在JavaScript数组中，数组是对象，并且值存储在散列表中，就像常规的对象值一样。 因此：
- 访问 – O（1）
- 追加 – 摊销O（1）（有时需要调整散列表的大小，通常只需要插入）
- 由于它需要重新分配所有索引，所以通过
unshift预先计划-O（n） - 插入 – 如果值不存在，则分摊为O（1）。 O（n）如果你想改变现有的值（例如，使用
splice）。 - 删除 – 摊销O（1）删除一个值，O（n）如果你想通过
splice重新分配索引。 - 交换 – O（1）
一般来说，在字典中设置或取消设置任何键都会被分摊到O（1），对于数组也是如此，而不pipe索引是什么。 任何需要重新编号现有值的操作都是O（n），因为您必须更新所有受影响的值。
你提到的所有复杂性都很好。 但是，如果数组对象保持长度，那么追加也可以在O（1）时间完成。
