为什么时间复杂度是 O(n!) 而不是 O(n * n!)

Question

这是一个 link to a youtube video @ 11:50，它显示了以下递归树：

代码如下：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def helper(curr: List[int], remains: List[int], res: List[List[int]]):
            if not remains:
                res.append(curr)
                return
            
            for i in range(len(remains)):
                next_num = remains[i]
                helper(curr + [next_num], [num for num in remains if num != next_num], res)
                
        helper([], nums, res)
        return 

视频说有O(n!)函数调用，不过好像有点多所以大概是这样，但是每一步我们都要为新的剩余数组复制最坏的 n 个元素，那为什么不变成 O(n * n!)

Answer 1

对于 n 参数列表，helper 对包含 n-1 个元素的列表进行 n 递归调用。这意味着它的运行时间是 T(n) = n*T(n-1)。求解 T 得到 n!，如果你自己展开几轮就很明显了：

T(n) = n * T(n-1)
     = n * (n-1) * T(n-2)
     = n * (n-1) * (n-2) * T(n-3)
     = ...
     = n! * T(0)

如果它对 n-1 个元素的列表进行 一次 递归调用，它将是 O(n*n)。