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

Question

我正在尝试解决LeetCode上的这个问题：https://leetcode.com/problems/factor-combinations/description/ 可以将数字视为其因子的乘积。例如：

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);
            }            
            
        }
        
    }

- KBR

---

关于哪个变量的时间复杂度？ - Oliver Charlesworth

好的，但请记住它会剧烈波动 - 例如127只有一个输出，而128有很多。 - Oliver Charlesworth

嗯，我对最坏情况下的复杂度很感兴趣。 - KBR

“最坏情况”在这里是什么意思？（我并不想刁难你，我只是试图指出你的问题可能因为提问方式不当而不合理。） - Oliver Charlesworth

好的，我编辑了问题。最坏情况意味着，在计算给定n的组合因子数时，递归调用/迭代次数的最大值。 - KBR

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)

解决递归函数

希望这对您有所帮助。

- Ali Soltani

---

感谢Ali详细解答。如果我需要更简化的理解方式。第一次调用getFactorsHelper时，总共有n个可能的迭代（因为存在2到n的循环）。我困惑的部分是弄清楚每次迭代中所完成的工作。 - KBR

@KBR 抱歉，我在计算循环顺序时犯了一个错误！！我已经重新解决了。请查看。 - Ali Soltani

谢谢，阿里。所以它是O(nlogn)……对吗？抱歉问这个问题，因为有些数学符号我正在努力回忆我大学时代的知识。 - KBR

@KBR 是的，O(nlnn) = O(nlogn)。 - Ali Soltani

嗨@AliSoltani，你能帮忙看一下这个解决方案吗？KBR发布的解决方案在Leetcode上大约需要210毫秒，而下面的解决方案只需要2毫秒。根据你的分析，慢的解决方案是O(nlogn)，那么快的解决方案应该是O(n)吧？ - JohnnyHuo

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);
       }
   }
}}

- JohnnyHuo