这个的时间复杂度是多少？我想是O（n），但不是吗？

Question

这个的时间复杂度是多少？我想是O（n），但不是

def f5(n):
    for i in range(0,n,2):
        print(i)  
    if n<=0:
        return 1
    else:
        return 1 + f5(n-5)

Answer 1

不，这是O（n²），因为当您考虑从0..n运行的递归调用时，它本质上是一个嵌套循环。注意：外部递归调用“循环”以5步为单位运行，显式函数体循环以2步为单位运行，但在考虑时间复杂性时，始终忽略这些常量因素。例如，如果递归调用是n // 2，则完全是另一回事（即log（n）本身，与线性内部循环相结合，会产生O（n log（n））个嵌套循环）