你好，我刚刚解决了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(如果n是2的幂，则为2 x 2 x 2 ... x 2(，但我一直在理解这棵树的分支因子。
任何计算该算法时间复杂性的帮助都是受欢迎的，但我非常感谢有一种直观的方式来看待它(我可以在采访中复制这一点(。。。更正式的方法也是受欢迎的。
编辑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))运行时。。。那么我的问题-->哪种分析是正确的？
一个观察结果：
在最坏的情况下，当n是连续数个最小素数的乘积时，n的因子数发生。即2*3*5*7*11等
我很好奇这个数字作为n的函数增长得有多快(同样，在最坏的情况下(。使用Python，观察前100个左右的素数，n的基于10的对数似乎比n中的因子数量增长得快一点。对于小值，数字几乎相同，但差异越来越大，在70个左右的因子(即70个第一素数的乘积(之后，对数是因子数量的两倍多。
另一种说法是CCD_ 21比CCD_。
时间复杂性的一般情况是T(n) = sum_{i=1}{number of factors of n}(T(n/f_i)) + c(f_is是n的因子(。如果是n = 2^k，则时间复杂度为T(n) = log(n) T(n/2) + c。因此：
T(n) = log(n) T(n/2) + c =
log(n) (log(n/2) T(n/2^2) + c) + c =
log(n) log(n/2) T(n/2^2) + c (1 + log(n)) =
k * (k-1) * T(n/2^2) +c (1 + k) =
k * (k-1) * (log(n/2^2) T(n/2^3) + c) + c (1 + k) =
k * (k-1) * (k-2) T(n/2^3) +c (1 + k + k * (k-1)) = Omega(log(n)!)
我们使用了Omega，因为它只是针对2^k的情况。要想了解更多关于复杂性的信息，您需要对一般术语进行更多的仔细检查。