时间 Space 递归函数的复杂度

Question

这是一个 leetcode 问题：https://leetcode.com/problems/reverse-string/solution/

编写一个反转字符串的函数。输入字符串以字符数组形式给出 char[].

不要为另一个数组分配额外的 space，您必须通过使用 O(1) 额外内存就地修改输入数组来执行此操作。

示例：

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

解决方案 1：

class Solution:
    def reverseString(self, s):
        def helper(left, right):
            if left < right:
                s[left], s[right] = s[right], s[left]
                helper(left + 1, right - 1)

        helper(0, len(s) - 1)

时间复杂度：执行 N/2 交换的时间为 O(N)。 Space 复杂度：O(N) 以保持递归堆栈。

解决方案2：

class Solution:
    def reverseString(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left, right = left + 1, right - 1

时间复杂度：O(N) 交换 N/2 元素。 Space 复杂度：O(1)，它是一个常量 space 解。

有人能解释一下为什么解决方案 2 中的 space 复杂度是 O(1) 而解决方案 1 中的 space 复杂度是 O(n) 吗？

是不是方案一需要函数调用？

提前致谢！

Answer 1

当您递归调用一个函数时，会在后台创建一个新的堆栈框架来保存您在新调用中创建的 return 地址和变量。

每个递归调用都这样做，所以如果一个函数调用自身 n/2 次，那就是 O(n) 存储 space.

时间 Space 递归函数的复杂度

Time Space Complexity of Recursive Functions

python

recursion

time-complexity

space-complexity