再帰的および末尾再帰的コードの実行時および領域の複雑さ

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

ことがあるサブセットの数だと、あなたが返されるリストにそれぞれ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)); 
    } 
}