python - 这个嵌套 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 时执行，因此它们只是对一项重要但恒定的工作量的简明描述。最多 2500 print语句被执行。 2500 和任何常数一样，与渐近复杂度无关。只有极限内的行为(即随着 n 无限增长)才是重要的。

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