JavaScript数组的大O-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

JavaScript数组的大O

保持可爱mmm 2020-02-10 16:02:49 325

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

JavaScript 前端开发
分享到
取消 提交回答
全部回答(2)
  • 保持可爱mmm
    2020-02-14 11:58:30

    与大多数使用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),这仅仅是因为您必须更新所有受影响的值。

    0 0
  • 罗思雨
    2020-02-12 14:50:33

    开发者您好, 对于一些高级程序语言的,它的元素类型没有严格的要求,它有一个标准的叫法叫做泛型,它就是说任何一个单元类型都可以放进去。 对于数组,它底层的硬件实现,有一个叫内存管理器的东西,每当你申请数组的话,计算机实际上是在内存中,给你开辟了(申请了)一段连续的地址,每一个地址都可以直接通过内存管理器进行访问。这张图里示意的地方就是它相应的内存地址。直接访问方面,它访问第一个元素和访问中间某个元素,时间复杂度都是一样的。也就是常数时间称为O(1)。从这里可以总结出它可以进行随机地访问任何的一个元素,访问速度非常快,这也是它的特性之一。 对于JS,假如有一个数组含有ABCEFG,我们想把元素D插入到数组中输出ABCDEFG。这个时候需要把EFG往下挪一个位置,而这样的操作导致了时间复杂度不再是常数级了,而是O(n)的时间复杂度。在最坏的情况甚至需要挪动整个数组;最好的情况下插入到最后面就变成了O(1);平均情况下需要移动一半的元素位置。同理可得,进行删除操作的时候一样。平均时间复杂度O(n)。 由此可见,如果对数组进行大量的增删操作,它会涉及到非常多的array copy,这样它的时间复杂度不是特别高效的。其实这个问题不仅仅存在于JS,Java也是如此,举个例子,ensure capacity 所进行的操作其实相对暴力,它会先查找整个数组的实际长度,如果长度够的话就什么都不做;如果长度不够的话,那么它会直接new一个新的数组出来,新的数组长度是当前长度乘以2,把老数组的值拷贝到新数组上面去。

    针对您说的,是否在工作中动态扩展阵列或其他一些性能提升算法?我觉得您可以参考工业上那些已经千锤百炼的老代码,他们的做法,从两点触发:空间换时间、升维。

    祝您在喜欢的技术道路上越走越好

    2 0
添加回答
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题
推荐课程