python - 2个函数的时空复杂度

Question

def bar(n):
    if n==0:
        return 0
    else:
        return n+bar(n-1)
def foo(n):
    if n==0:
        return 0
    else:
        return bar(n)+foo(n-1)

嗨，我刚刚了解了空间和时间复杂性。任何人都可以向我确认我是否正确地说 foo 的时间复杂度是 O(n**2) 而 foo 的空间复杂度是 O(n) ？不太确定时间复杂度，因为 foo 调用 bar 只调用自己一次，而 foo 总是调用 2 个函数。

Answer 1

你是对的。这里的空间复杂度实际上是程序执行过程中调用栈的最大深度，为O(n)。对于 foo 的时间复杂度，您可以计算函数调用的次数:

NC(foo(n)) = NC(bar(n)) + NC(foo(n-1)) + 1

由于 NC(bar(n)) = n + 1 很明显，我们有(忽略那些常量“+ 1”部分):

NC(foo(n)) = n + NC(foo(n-1)) = n + (n-1) + NC(foo(n-2)) = 
= n + (n-1) + ... + 1 = n(n+1)/2 = O(n^2)