代码之家 › 专栏 › 技术社区 › kiki

确定递归函数的时间和空间复杂度

space-complexity big-o time-complexity recursion python

0

kiki · 技术社区 · 7 年前

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

如何根据输入n计算foo运行时间的时间复杂度?空间复杂性如何?

2 回复 | 直到 7 年前

1

cs95 abhishek58g 7 年前

 return n * bar(n)
      â n * (1 + bar(n - 1))
      â n * (1 + 1 + bar(n - 2))
      â n * (1 + 1 + 1 + bar(n - 3))
      â n * (1 + 1 + 1 + .... <n times> + bar(0))
      â n * n

这在时间和内存上呈线性- O(n) .

2

0

arunk2 7 年前

对于运行时和空间。

让我试着用递归关系和推导来解释它。

对于运行时

Base case: T(0) = 1
Recurion : T(n) = T(n-1) + 1  (constant time for addition operation)


T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 1 + 1 + 1
     = T(n-4) + 1 + 1 + 1 + 1
     = T(n-4) + 4*1
     ...
     = T(n-n) + n * 1
     = T(0) + n * 1
     = 1 + n
     = O(n)

对于空间复杂性

因此,O(n)空间。

通过尾部递归实现,可以进一步降低空间复杂度。

希望有帮助!