遞歸和尾遞歸代碼的運行時間和空間複雜度

Question

下面的代碼查找一組數字的所有子集的複雜性如何？

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

Answer 1

在我看來，這裏的主要問題是數據空間的複雜性。如果原始數組的長度超過幾十個，您的代碼將拋出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)); 
    } 
}