以下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)until nis 1。该函数将进行n此类调用，因此其复杂性为O(n).