这个递归函数的时间复杂度

-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

这个递归函数的时间复杂度

回答

相关问题