python - 以下python函数的时间复杂度是多少？

Question

def func(n):
    if n == 1:
        return 1
    return func(n-1) + n*(n-1)

print func(5)

变得困惑。不确定它到底是什么。是 O(n) 吗？

Answer 1

计算n*(n-1) 是固定时间操作。该函数有趣的部分是调用 func(n-1) 直到 n 为 1。该函数将进行 n 次这样的调用，因此其复杂度为 O(n)。