时间戳

首页 > 解决方案 > 为什么时间复杂度 O(n!) 不是 O(n * n!)

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

问题描述

这是 youtube 视频@ 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!)

标签： pythonalgorithmpermutation

解决方案

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

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

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

推荐阅读