具有多个条件的for循环的大O.

Question

我不知道之前是否有人问我,因为我不确定如何制定我的搜索,但我会尝试.下面这段代码的大O是什么？

List<SomeObject> list = //... List is created here    .1

int sum = 0;                                          .2

for(int i = 0; i < list.size() && i < 75000; i++){    .3
    sum++;                                            .4
}

我看到它的方式是第1,2和4行是O(1).然后第3行是O(N),因为它每次调用时都不会花费相同的时间.列表的大小将影响迭代量.这意味着整个代码块最终为O(N).或者这完全是胡说八道？

Answer 1

列表创建不一定是O(1),可以是O(N).

第2行显然是O(1).

我认为循环也是O(1),因为它限制为75000个条目,所以有一个上限.没有i <75000限制,它将是O(N),正如你所说的那样.

所以第2-4行我会说是O(1),第1行真的取决于你省略的列表创建过程.