java ArrayList的时间复杂度

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (572)

ArrayListjava中的数组还是列表?什么是get操作的时间复杂度,是它O(n)还是O(1)

提问于
用户回答回答于

一个ArrayList在Java是一种List由一个支持array

get(index)方法是一个恒定的时间O(1),操作。

代码直接出自Java库,用于ArrayList.get(index)

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

基本上,它只是直接从支持数组中返回一个值。(RangeCheck(index))也是恒定的时间)

用户回答回答于

它的实现是用数组完成的,get操作是O(1)。

javadoc说:

size,isEmpty,get,set,iterator和listIterator操作在恒定时间内运行。add操作以分摊的恒定时间运行,即添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行(粗略地说)。与LinkedList实现相比,常数因子较低。

所属标签

可能回答问题的人

  • 华讯云

    0 粉丝0 提问7 回答
  • gulu丶咕噜

    0 粉丝1 提问5 回答
  • 女淘日记

    杭州吱吱吱科技 · 站长 (已认证)

    1 粉丝1 提问3 回答
  • 卓脑域名

    0 粉丝0 提问3 回答

扫码关注云+社区

领取腾讯云代金券