如何寻找dfs+backtracking算法的时间复杂度？

Question

我正试图在leetcode https://leetcode.com/problems/factor-combinations/description/上解决这个问题

数字可以看作是其因素的乘积。例如 8=2x2x2；=2x4。

编写一个接受整数n的函数，并返回它的所有因素的所有可能组合。

虽然我能够使用dfs方法编写代码，但我很难在输入方面驱动其最坏的情况时间复杂性。有人能帮忙吗？

 public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> current = new ArrayList<Integer>();
        getFactorsHelper(n,2,current,result);
        return result;
    }
    
    
    public void getFactorsHelper(int n,int start,List<Integer> current, List<List<Integer>> result){
        if(n<=1 && current.size()>1){
            result.add(new ArrayList<>(current));
            return;
            
        }
        for(int i=start;i<=n;i++){
          
            if(n%i==0) {
                current.add(i);
                getFactorsHelper(n/i,i,current,result);
                current.remove(current.size()-1);
            }            
            
        }
        
    }

Answer 1

我计算了代码的复杂性，如下所示：

让我们考虑runtime of getFactorsHelper(n,2)是函数T(n)。

在下面的部分，您有一个带有i索引的循环。

for(int i=start;i<=n;i++){    
            if(n%i==0) {
                current.add(i);
                getFactorsHelper(n/i,i,current,result);
                current.remove(current.size()-1);
            }              
        }

在每次迭代中，n被i除以。所以我们有：

(第一次迭代)

getFactorsHelper(n/2,2,current,result) = T(n/2) 

(第二次迭代)

getFactorsHelper(n/3,3,current,result) <= getFactorsHelper(n/3,2,current,result) = T(n/3) 

(第三次迭代)

getFactorsHelper(n/4,4,current,result) <= getFactorsHelper(n/4,2,current,result) 
= T(n/4) 

…

(最后迭代)

getFactorsHelper(n/n,n,current,result) <= getFactorsHelper(n/n,2,current,result) = T(n/n) = T(1) 

总成本

T(n) <= T(n/2) + T(n/3) + T(n/4) + ... + T(1)

求解递归函数

​

​

我希望这能帮到你。

Answer 2

无法在评论中发布解决方案。@AliSoltani https://discuss.leetcode.com/topic/30752/my-short-java-solution-which-is-easy-to-understand发帖作为另一个答案

public class Solution {
public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    if(n <= 3)  return ret;
    List<Integer> path = new LinkedList<Integer>();
    getFactors(2, n, path, ret);
    return ret;
}

private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){
   for(int i = start; i <= Math.sqrt(n); i++){
       if(n % i == 0 && n/i >= i){  // The previous factor is no bigger than the next
           path.add(i);
           path.add(n/i);
           ret.add(new LinkedList<Integer>(path));
           path.remove(path.size() - 1);
           getFactors(i, n/i, path, ret);
           path.remove(path.size() - 1);
       }
   }
}}