这个嵌套for循环的时间复杂度是多少？

Question

我在python中有以下代码:

def mystery(n):
    if n <= 50 :
        for i in range(n) :
            for j in range(n) :
                print i*j
    else :
        mystery(n-1)

对于以下嵌套for循环:

for i in range(n) :
    for j in range(n) :

对于每个i人来说n,要j经过n多次迭代i.所以不应该复杂O(n^2)吗？但是,我的同行告诉我它不是,有人可以提供解释为什么？

Answer 1

这些循环只在执行时执行n <= 50,因此它们只是对一个非常重要但不变的工作量的简明描述.最多print执行2500条语句.像任何常数一样,2500与渐近复杂性无关.只有极限中的行为(即n无限制地增长)才是重要的.

对于较大的n,该函数仅从n向下计数到50.该部分花费O(n)时间,因此整体的时间复杂度mystery是线性的.