递归和尾递归代码的运行时间和空间复杂度

下面的代码查找一组数字的所有子集的复杂性如何？递归和尾递归代码的运行时间和空间复杂度

public List<List<Integer>> subsets(int[] nums) { 
     List<List<Integer>> subsets = new ArrayList<>(); 
     subsets.add(new ArrayList<Integer>()); 
     return find(subsets, nums, 0); 
    } 

    private List<List<Integer>> find(List<List<Integer>> subsets, int[] nums, int index) { 
     if (index == nums.length) { 
      return subsets; 
     } 
     List<List<Integer>> newSubsets = new ArrayList<>(); 
     for (List<Integer> subset: subsets) { 
      List<Integer> newSubset = new ArrayList<>(); 
      newSubset.addAll(subset); 
      newSubset.add(nums[index]); 
      newSubsets.add(newSubset); 
     } 
     subsets.addAll(newSubsets); 
     return find(subsets, nums, index + 1); 
    }

难道O(2^nums.length)做为所子集的数量也有，你必须添加每一个到返回的列表？另外，我是否认为下面的版本仍然渐近O(2^set.size())，但是由一般递归贡献的空间复杂度是O(set.size())，而在上面的尾递归代码中，它是O(1)？

public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set) { 
    ArrayList<ArrayList<Integer>> subsets = new ArrayList<>(); 
    getSubsets(set, subsets, 0); 
    return subsets; 
} 

private static void getSubsets(ArrayList<Integer> set, ArrayList<ArrayList<Integer>> subsets, int index) { 
    if (index == set.size()) { 
     subsets.add(new ArrayList<Integer>()); 
     return; 
    } 
    getSubsets(set, subsets, index + 1); 
    int item = set.get(index); 
    ArrayList<ArrayList<Integer>> moreSubsets = new ArrayList<>(); 
    for (ArrayList<Integer> subset: subsets) { 
     ArrayList<Integer> newSubset = new ArrayList<>(); 
     newSubset.addAll(subset); 
     newSubset.add(item); 
     moreSubsets.add(newSubset); 
    } 
    subsets.addAll(moreSubsets); 
}

来源

2017-08-25 ion20

Java没有做尾调用消除。 – user2357112

...但现在你只是将递归转换为迭代的一个步骤。它会运行得稍微快一些，但不会因缺少方法调用而节省太多内存。经过几次迭代后，子集将分配比堆栈多得多的内存。 – Selindek

在我看来，这里的主要问题是数据空间的复杂性。如果原始数组的长度超过几十个，您的代码将抛出OutOfMemoryError。地球上的更多元素和所有内存芯片和硬盘驱动器都不足以存储子集。

通过优化尾部递归来保存几个字节并没有什么区别。

出于实用目的，以下代码非常有效。尽管一般来说速度较慢，但它的数据空间复杂度为O（N），它可以即时计算子集，因此如果只想处理某些子集，它甚至可以为您提供更好的结果。

private static List<Integer> getSubset(int[] nums, BigInteger n) { 
    List<Integer> subset = new ArrayList<>(); 
    for (int i = 0; i < nums.length; i++) { 
     if (n.testBit(i)) { 
      subset.add(nums[i]); 
     } 
    } 
    return subset; 
}

您可以访问子集是这样的：

public static void main(String... args) { 
    int[] nums = { 1, 2, 3, 4 }; 
    for (BigInteger n = new BigInteger("2").pow(nums.length).subtract(BigInteger.ONE); n 
      .compareTo(BigInteger.ZERO) >= 0; n = n.subtract(BigInteger.ONE)) { 
     // process nth subset 
     // each subset is identified by n where 0<=n<2^nums.lenght 
     System.out.println(getSubset(nums, n)); 
    } 
}

来源

2017-08-26 08:13:51 Selindek

递归和尾递归代码的运行时间和空间复杂度

回答

相关问题