带多条件限制的for循环的Big O时间复杂度咨询及分析验证

首先直接说结论：你的分析不正确，这段代码的整体时间复杂度是O(1)（常数时间），而非O(N)。下面给你详细拆解原因：

先把代码清晰列出来：

List<SomeObject> list = //... List is created here 
int sum = 0; 
for(int i = 0; i < list.size() && i < 75000; i++){ 
    sum++; 
}

关键误区：循环的执行次数有固定上限 #

你之前认为循环是O(N)，是只考虑了i < list.size()这个条件，但忽略了第二个条件i < 75000——这意味着循环的执行次数有一个固定的上限75000次：

• 如果列表长度N ≤ 75000：循环执行N次，但N的最大值被限制在75000，不会随输入规模无限增长；
• 如果列表长度N > 75000：循环只会执行75000次，之后i <75000的条件不满足，循环终止。

而Big O复杂度描述的是当输入规模趋近于无穷大时，算法的时间增长趋势。当N（列表长度）变得极大时，这段代码的循环次数始终停留在75000次，不会随着N的增长而增加，所以这部分的时间复杂度是O(1)。

逐行复杂度拆解 #

• 第1行（列表赋值）：只是引用赋值操作，时间复杂度O(1)；
• 第2行（sum初始化）：简单变量赋值，O(1)；
• 循环部分：不管N多大，循环最多执行75000次，每次循环里的sum++是O(1)操作，整体循环的时间复杂度是O(1)；
• 循环内的sum++：属于单次O(1)操作，不改变整体复杂度。

综上，整个代码块的时间复杂度是O(1)。

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