Java中返回ArrayList的getAvailableRobots方法时间复杂度是多少？

结论 #

你给出的代码实现中，getAvailableRobots()方法的时间复杂度为 O(1)，执行List<Robot> newList = getAvailableRobots();的耗时也恒定为O(1)，不存在O(n)级别的开销。

原理说明 #

Java中所有对象类型的传递都是引用传递，你的方法逻辑仅仅是返回available成员所持有的引用值（即堆内存中ArrayList实例的存储地址），赋值操作也只是把这个地址复制给新的变量newList，全程不会遍历列表中的元素，也不会创建新的列表实例，因此不会随列表元素数量增加产生额外耗时。

什么场景会出现O(n)复杂度？ #

只有当你在get方法中做防御性拷贝时，才会产生O(n)的时间开销，常见的拷贝写法如下：

// 方法1：通过构造器拷贝生成新列表
public List<Robot> getAvailableRobots(){
    return new ArrayList<>(available);
}

// 方法2：通过流操作生成不可变新列表
public List<Robot> getAvailableRobots(){
    return available.stream().toList();
}

这种写法的目的是避免外部拿到引用后修改内部的available成员，会遍历所有元素生成新的列表实例，时间复杂度为O(n)，你可以根据是否需要隔离内部状态选择对应的实现。

内容的提问来源于stack exchange，提问作者Martin