这个嵌套 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) :

对于 n 中的每个 i，j 迭代 n 多达 i 次。那么复杂度不应该是O(n^2)吗？但是，我的同事告诉我不是，谁能解释一下为什么？

Answer 1

这些循环仅在 n <= 50 时执行，因此它们只是对重要但恒定的工作量的简要描述。最多执行 2500 print 条语句。 2500 和任何常数一样，与渐近复杂度无关。只有极限内的行为（即随着 n 无限增长）才是重要的。

对于较大的n，函数只是从n倒数到50。这部分需要O(n)的时间，因此mystery整体的时间复杂度是线性的。