JavaScript数组的大O(Big O of JavaScript arrays)

在JavaScript中数组是很容易的添加和删除项目进行修改。 这一定程度上掩盖了事实，大多数语言数组是固定大小的，并且需要复杂的操作来调整。 似乎的JavaScript可以很容易地编写表现不佳的阵列码。 这导致了一个问题：

我可以从JavaScript实现期望的问候阵列的性能表现是什么（在大O时间复杂性方面）？

我认为所有合理的JavaScript实现至少有以下大O的。

• 访问 - O（1）
• 追加 - O（N）
• 预谋 - O（N）
• 插入 - O（n）的
• 删除 - O（N）
• 交换 - O（1）

JavaScript允许你预先填充的阵列到一定大小，使用new Array(length)的语法。 （加成问题：是以这种方式创建Ö阵列（1）或O（n））的这更像传统的阵列，并且如果用作预大小的数组，可以允许O（1）附加。 若添加循环缓冲器逻辑，可以实现O（1）预先考虑。 如果使用动态扩展阵列，O（log n）的将是这两个的平均情况。

我可以期待某些地方比这里我的假设更好的性能？ 我不希望任何事情在任何规格概述，但实际上它可能是所有主要实现在后台使用优化的阵列。 是否有动态扩展的阵列或一些其它的性能在工作中增强算法？

PS

我不知道这样做的原因是因为我研究了一些排序算法，其中大部分似乎认为追加和删除所描述他们的整体大O.时，O（1）操作

Answer 1:

与大多数的语言，与实施，以及阵列，阵列中，JavaScript数组是对象，并且值存储在哈希表中，就像普通的对象值。 因此：

• 访问 - O（1）
• 附加 - 摊销O（1）（有时调整散列表是必需的;通常，只需要插入）
• 预谋- O（n）的通过unshift ，因为它需要重新分配所有指标
• 插入 - 摊销O（1）如果该值不存在。 o如果您想转移现有值（例如，使用（n）的splice ）。
• 删除-平摊O（1）取一个值，为O（n），如果你想通过重新分配指数splice 。
• 交换 - O（1）

一般情况下，设置或注销一个字典任何键被摊销O（1），和同样不论索引是什么阵列。 这需要重编现有值的任何操作是O（n），只是因为你必须更新所有受影响的值。

文章来源: Big O of JavaScript arrays