這個遞歸函數的時間複雜度

-1

我有這個遞歸函數。我想知道這個算法的時間複雜度。這個想法給出了一個數字，我們必須找到所有的總結爲給定數這個遞歸函數的時間複雜度

public void getSequences(int n, ArrayList<Integer> buffer, int sum) { 
    if(sum == n) { 
    for(int j=0; j<buffer.size(); j++) { 
     System.out.print(buffer.get(j) + " "); 
    } 
    System.out.println(""); 
    } 

    for(int i=1; i<n; i++) { 
    sum += i; 
    if(sum > n) { 
     break; 
    } 
    buffer.add(i); 
    getSequences(n, buffer, sum); 
    sum -= i; 
    buffer.remove(i); 
    } 
} 

ArrayList<Integer> buffer = new ArrayList<Integer>(); 
getSequences(3, buffer, 0); 

// Output 
// 1 1 1 
// 1 2 
// 2 1

這是什麼算法的時間複雜度的子集？

來源

2014-10-22 rajan sthapit

複雜度爲O（k），其中k - 此類子集的數量 – Herokiller 2014-10-22 02:50:17

'buffer.remove（i）;'不正確並導致IndexOutOfBoundsException異常。我相信你的意思是'buffer.remove（buffer.size（） - 1）;'但是我試圖做的編輯被拒絕了，因爲沒有「維護海報的原意」。 – Nate 2014-10-22 13:45:33

由於代碼生成的每個可能的序列總和爲n，並且順序很重要。它的漸近複雜度受序列大小的限制。

計算所有序列的另一種方法是思考如下。

以n開頭1。

實施例：1 1 1 1 1
對於長度n-1的一些位集，減少相鄰序列如果該位是在該索引。

示例：位集合（0,1,0,0）產生序列：1（1 + 1）1 1 => 1 2 1 1

示例：位集合（1,1,0,1）的產率序列：（1 + 1 + 1）（1 + 1）=> 3 2

由於尺寸n-1的特定位集產生一個獨特的序列，則該算法顯然是O（2^N）。

來源

2014-10-22 02:53:50 Nate

這個遞歸函數的時間複雜度

回答

相關問題