我在 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)
吗? ?但是,我的同事告诉我不是,谁能解释一下为什么?
最佳答案
这些循环仅在 n <= 50
时执行,因此它们只是对一项重要但恒定的工作量的简明描述。最多 2500 print
语句被执行。 2500 和任何常数一样,与渐近复杂度无关。只有极限内的行为(即随着 n 无限增长)才是重要的。
对于较大的 n,函数只是从 n 倒数到 50。这部分需要 O(n) 时间,因此时间复杂度为 mystery
。整体呈线性。
关于python - 这个嵌套 for 循环的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28142398/