如何找到dfs +回溯算法的時間複雜度？

我試圖解決在本文給出了這個問題https://leetcode.com/problems/factor-combinations/description/如何找到dfs +回溯算法的時間複雜度？

數字可以被看作是其因素的產物。例如

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

     } 

    }

來源

2017-08-13 KBR

時間複雜度就什麼變化？ –

關於輸入n – KBR

好的，但請記住，它將大幅波動 - 例如127只有一個輸出，而128有負載。 –

我計算代碼的複雜性是這樣的：

讓我們考慮的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)

解決遞歸函數

我希望這可以幫助你。

來源

2017-08-13 19:38:03

感謝阿里詳細解答了答案。如果我必須以更簡化的方式理解，第一次調用getFactorsHelper時，總共有n次可能的迭代（因爲for循環爲2到n）。我感到困惑的部分是要弄清楚每次迭代中完成的工作。 – KBR

@KBR對不起，我在計算循環順序時犯了一個錯誤！我又解決了它。請看看它。 –

謝謝阿里。所以它的O（nlogn）..好嗎？對不起，因爲我想從大學時候開始回憶起這些數學符號 – KBR

無法在評論中發佈解決方案。郵政這裏另一種答案@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); 
     } 
    } 
}}

來源

2017-09-19 06:50:41 JohnnyHuo

如何找到dfs +回溯算法的時間複雜度？

回答

相關問題