关于这段Python代码的渐近时间复杂度及打印次数问题咨询

代码回顾 #

def func(s):
    for i in range(s):
        if i == 0:
            for j in range(s):
                for k in range(10000):
                    print("ffff")

1. 渐近时间复杂度 #

外层for i in range(s)会执行s次，但只有当i == 0时才会进入内层嵌套循环。内层j循环执行s次，每次j循环里k循环固定执行10000次。总执行次数为s * 10000，渐近时间复杂度忽略常数系数，因此是O(s)（线性时间复杂度）。

2. "ffff"的打印次数 #

只有当i=0时才会触发打印逻辑：j循环跑s次，每次j循环里k循环跑10000次，所以打印次数是s * 10000，和s成线性正比关系——外层i循环除了第一次，其余s-1次都不会执行任何嵌套循环，因此不会出现平方级的次数。

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