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

Question

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

如何根据输入 n 计算 foo 运行时间的时间复杂度？ space 复杂度如何？

Answer 1

让我们分解一下：

 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)。

Answer 2

正如 cᴏʟᴅsᴘᴇᴇᴅ 所提到的，运行时和 space.

都是 O(n)

我试着用递归关系和推导来解释一下

对于运行时

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)

对于space复杂度

将为所有递归调用创建'n' 堆栈。因此，O(n) space.

注意： space 复杂性可以通过尾递归实现进一步降低。

希望对您有所帮助！

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

Determining time and space complexity of a recursive function

python

recursion

big-o

time-complexity

space-complexity