python-3.x - 这个函数的时间复杂度是多少，它生成一个数字的所有唯一因子组合？

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)但我一直在理解这棵树的分支因子。

欢迎任何计算此算法时间复杂度的帮助，但我将非常感谢以直观的方式来看待它(我可以在采访中复制的东西)...也欢迎使用更正式的方法。

编辑 1:

所以我可以说这次重复有log(n)分支机构(因素数量)和log(n)最坏情况下的深度导致运行时间为 O(log(n)^log(n))这个推理好吗？

编辑 2:

然而，另一种看待它的方式是我们有 O(log(n))因素，我们只是在做所有可能组合的一个子集，即 2^n锻炼从而导致2^log(n) = n不同的解决方案。对于每个 n我们拥有的解决方案 log(n) (树深度)乘法产生 O(nlog(n))运行时...所以我的问题 --> 哪个分析是正确的？

Answer 1

一个观察:

n 的因子数在最坏情况下发生在 n 是连续多个最小素数的乘积时。 IE。 2*3*5*7*11等

我很好奇这个数字作为 n 的函数增长的速度有多快(同样，在最坏的情况下)。使用 Python，并查看前 100 个左右的素数，n 的以 10 为底的对数似乎比 n 中的因子数增长得快一点。对于小值，数字几乎相同，但差异不断变大，在 70 个左右的因子(即 - 70 个第一个素数的乘积)之后，对数是因子数的两倍多。

另一种表达方式是 [n 的因子数] 比 log n 增长得慢。