java - 如何求dfs+回溯算法的时间复杂度？

Question

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

Numbers can be regarded as product of its factors. For example

8 = 2 x 2 x 2; = 2 x 4.

编写一个函数，它接受一个整数 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

我这样计算你的代码的复杂度:

让我们考虑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)

求解递归函数

希望对您有所帮助。