3

我試圖解決在本文給出了這個問題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); 
      }    

     } 

    } 
+0

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

+0

關於輸入n – KBR

+0

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

回答

4

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

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

ni在每次迭代分割。因此,我們有:

(第一次迭代)

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) 

解決遞歸函數

order

我希望這可以幫助你。

+0

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

+0

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

+0

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

0

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