get()
方法获取一个元素,如果这个元素符合某些条件,它就会被添加到一个新的数组列表中,使用add()
方法实现。List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
Item toCheck = items.get(i);
if(toCheck meets some condition){
lessItems.add(toCheck);
}
}
我不确定这里的时间复杂度是什么。因为我对所有的项都调用了get()方法,所以这是O(n)。然后我也可能对所有的项调用add()方法,所以又有一个O(n)。这一点不太确定。
O(n)
。请看我的回答。 - hqtO(n)
。之后是一些常数时间的操作,数量不是2。他们不应该像@Elliott在之前的评论中那样说。将O(n) + O(n)
简单相加是错误和不准确的,因为第二个复杂度是嵌套在第一个内部的(也就是说,不是简单相加,而是常数项的乘积);它是cn = O(n)
。 - ChiefTwoPencils