如何求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 和 return 其因子的所有可能组合。

虽然我能够使用 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) 的 runtime 是函数 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

无法post评论中的解决方案。 Post 作为另一个答案@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);
       }
   }
}}

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

How to find the time complexity of dfs+backtracking algorithms?

java

algorithm

recursion

time-complexity

depth-first-search