含固定次数嵌套循环与输入遍历的函数时间复杂度问询

大O复杂度的核心判定基准 #

大O记号的核心作用是描述算法运行时间随输入规模增长的变化趋势，而非统计代码执行的绝对次数。判定过程中需要始终锚定一个核心判断标准：代码段的执行次数，是否会随外部输入的规模变化而同步改变。所有和输入规模无关的固定执行次数，无论数值大小，都会被归为常数项，在化简时被剔除。

第一个疑问的解答 #

执行范围固定为0到10000的两层嵌套for循环，时间复杂度应判定为O(1)，而非O(10000²)。

• 10000是写死在代码里的固定常量，不会随任何外部输入的规模变化而改变，对应的总执行次数10000²也是一个固定值。
• 把固定常量的具体数值写进大O表达式的做法本身不符合大O的定义：大O是用来衡量规模趋近无穷时的增长速度，不是用来记录某次运行的绝对耗时。哪怕将循环范围调整为0到1亿，只要执行上界是固定值，对应的时间开销就属于常数级操作。

给定Python函数的整体复杂度计算 #

首先拆解函数的两段顺序执行代码的复杂度：

def test(arr):
    for i in range(10000):
        for j in range(10000):
            print("hello world")

    for num in arr:
        print(num)

• 第一段两层嵌套循环：执行次数固定为1000010000=1e8次，和输入arr的长度完全无关，属于O(1)*的常数开销。
• 第二段遍历arr的循环：执行次数完全等于arr的长度（即常规定义下的输入规模n），属于*O(n)*的线性开销。

根据顺序执行代码的复杂度计算规则：总复杂度等于各段复杂度的和，再剔除低阶项化简。本案例中总复杂度为O(1 + n)，由于当输入规模n趋近于无穷大时，固定常数的开销相对于线性增长的开销可以忽略，因此整个函数的最终时间复杂度为O(n)。

常见误区澄清 #

判定嵌套循环的复杂度时，永远不要只看循环的嵌套层数，核心判断标准是循环的执行上界是否和输入规模相关：

• 如果两层循环的范围是写死的固定值，无论嵌套多少层，都属于常数级开销；
• 如果两层循环的上界是由输入规模n决定的，哪怕只有两层，对应的复杂度也是O(n²)。

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