JavaScript数组的大O
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）运算。 问题来源于stack overflow
写回答
-
与大多数使用Java数组实现数组的语言相反，数组是对象，值存储在哈希表中，就像常规对象值一样。因此：
存取权-O（1） 追加-摊销O（1）（有时需要调整哈希表的大小；通常仅需要插入） 通过前置-O（n）unshift，因为它需要重新分配所有索引 插入-如果值不存在，则摊销O（1）。如果要移动现有值（例如，使用splice），则为O（n ）。 删除-分摊O（1）以删除值O（n）（如果要通过分配索引）splice。 交换-O（1） 通常，设置或取消设置dict中的任何键都是摊销O（1），对于数组，不管索引是什么，也是如此。需要重新编号现有值的任何操作都是O（n），这仅仅是因为您必须更新所有受影响的值。
2020-02-14 11:58:30赞同 展开评论 打赏 -
开发者您好， 对于一些高级程序语言的，它的元素类型没有严格的要求，它有一个标准的叫法叫做泛型，它就是说任何一个单元类型都可以放进去。 对于数组，它底层的硬件实现，有一个叫内存管理器的东西，每当你申请数组的话，计算机实际上是在内存中，给你开辟了(申请了)一段连续的地址，每一个地址都可以直接通过内存管理器进行访问。这张图里示意的地方就是它相应的内存地址。直接访问方面，它访问第一个元素和访问中间某个元素，时间复杂度都是一样的。也就是常数时间称为O(1)。从这里可以总结出它可以进行随机地访问任何的一个元素，访问速度非常快，这也是它的特性之一。 对于JS，假如有一个数组含有ABCEFG，我们想把元素D插入到数组中输出ABCDEFG。这个时候需要把EFG往下挪一个位置，而这样的操作导致了时间复杂度不再是常数级了，而是O(n)的时间复杂度。在最坏的情况甚至需要挪动整个数组；最好的情况下插入到最后面就变成了O(1)；平均情况下需要移动一半的元素位置。同理可得，进行删除操作的时候一样。平均时间复杂度O(n)。 由此可见，如果对数组进行大量的增删操作，它会涉及到非常多的array copy，这样它的时间复杂度不是特别高效的。其实这个问题不仅仅存在于JS，Java也是如此，举个例子，ensure capacity 所进行的操作其实相对暴力，它会先查找整个数组的实际长度，如果长度够的话就什么都不做；如果长度不够的话，那么它会直接new一个新的数组出来，新的数组长度是当前长度乘以2，把老数组的值拷贝到新数组上面去。
针对您说的，是否在工作中动态扩展阵列或其他一些性能提升算法？我觉得您可以参考工业上那些已经千锤百炼的老代码，他们的做法，从两点触发：空间换时间、升维。
祝您在喜欢的技术道路上越走越好
2020-02-12 14:50:33赞同 2 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
