此函数的时间复杂度是多少，它生成一个数字的所有唯一因子组合？

Question

您好，我刚刚解决了leetcode 254 [https://leetcode.com/problems/factor-combinations/]，此算法的目的是找到给定数字n的所有因子的唯一组合（例如：对于n = 8，我们返回[[2 x 2 x 2], [2 x 4]]）并编写了下面的代码：

def getFactors(self, n: int) -> List[List[int]]:
    def helper(n, cur, path, ind, factors):
        if cur == n:
            res.append(path[:])
            return

        for i in range(ind, len(factors)):
            if cur * factors[i] <= n:
                path.append(factors[i])
                helper(n, cur * factors[i], path, i, factors)
                path.pop()

    res = []
    helper(n, 1, [], 0, [num for num in range(2, n) if n % num == 0])
    return res if res != [[]] else []

[此算法的工作方式是迭代所有因子，然后将cur乘以我要迭代的因子，只要cur * factors[i] <= n我可以将该因子添加到我的path中并继续递归。

尽管我无法用n来计算时间复杂度。我可以说，在最坏的情况下，递归树的深度为log n（如果2 x 2 x 2 ... x 2为2的幂，则深度为n），但我坚持要理解该树的分支因子。

欢迎提供任何帮助计算此算法时间复杂度的帮助，但我非常感谢以直观的方式查看它（我可以在访谈中重复的内容...也欢迎使用更多正式的方法。

Answer 1

时间复杂度的一般情况是T(n) = sum_{i=1}{number of factors of n}(T(n/f_i)) + c（f_i是n的因数。]