非嵌套双for循环的Big O时间复杂度判定咨询

问题说明 #

已知单个for循环的时间复杂度为O(N)，嵌套for循环的时间复杂度为O(N²)，现咨询以下两个非嵌套for循环的时间复杂度是否为O(N)？

示例代码如下：

def ex(W):
    for i in range(len(W)):
        if i == ...:
           return 
    for c in range(len(W)):
        if c == ...:
           return

由于每个循环最多运行N次，是否整体时间复杂度为O(N)？

结论及分析 #

• 整体时间复杂度确实是O(N)。
• 大O表示法关注的是输入规模增大时的渐进增长趋势，当两个线性时间的操作（每个都是O(N)）依次执行时，总时间为O(N) + O(N) = O(N)——因为我们只保留最高阶项，常数系数会被忽略，2N的增长速度和N是一致的，所以归为O(N)。
• 对应到你的代码：最坏情况下第一个循环遍历完所有N个元素才退出，接着第二个循环也遍历完N个元素，总执行次数是N + N = 2N，这完全符合O(N)的定义——存在常数C（比如取2）和足够大的N₀，当输入规模N≥N₀时，总执行次数不会超过C*N。

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