这是集算法实际上是O（n）的空间复杂度？ [英] Is the space complexity of this subset algorithm actually O(n)?
问题描述
这是问题9.4来自破解编码面试5 日
的问题：写方法返回一个集合的所有子集
This is problem 9.4 from Cracking the Coding Interview 5th
The Problem: Write a method to return all the subsets of a set.
下面是我在Java解决方案。（测试它，它的工作原理！）
Here is my solution in Java.(tested it, it works!!!)
public static List<Set<Integer>> subsets(Set<Integer> s) {
Queue<Integer> copyToProtectData = new LinkedList<Integer>();
for(int member: s) {
copyToProtectData.add(member);
}
List<Set<Integer>> subsets = new ArrayList<Set<Integer>>();
generateSubsets(copyToProtectData, subsets, new HashSet<Integer>());
return subsets;
}
private static void generateSubsets(Queue<Integer> s,
List<Set<Integer>> subsets, Set<Integer> hashSet) {
if(s.isEmpty()) {
subsets.add(hashSet);
} else {
int member = s.remove();
Set<Integer> copy = new HashSet<Integer>();
for(int i:hashSet) {
copy.add(i);
}
hashSet.add(member);
Queue<Integer> queueCopy = new LinkedList<Integer>();
for(int i:s){
queueCopy.add(i);
}
generateSubsets(s, subsets, hashSet);
generateSubsets(queueCopy, subsets, copy);
}
}
我看了看这个问题的解决方案，并撰文说，要解决这个算法运行的 O（2 N ）的时间复杂度和的 O（ 2 N ）的空间复杂度。我同意她的看法，该算法在运行的 O（2 N ）的时间，因为要解决这个问题，你必须考虑到的任何元素，你有两种可能的事实，它可以是在设定与否。因为你有n个元素，您的问题将有2 N 的可能性，所以这个问题将与O（2 N ）及时解决。
I looked at the solutions for this problem and the author said that the solution to this algorithm runs in O(2n) time complexity and O(2n) space complexity. I agree with her that this algorithm runs in O(2n) time because to solve this problem, you have to consider the fact that for any element, you have two possibilities, it can either be in the set or not. And because you have n elements, your problem will have 2n possibilities so the problem would be solved with O(2n) time.
不过，我相信，我有我的算法中的 O（N）的空间中运行一个令人信服的理由。我知道，空间复杂度是采取的一种算法相对于该输入大小的总空间 空间复杂，是相对于一个递归调用的深度（记住了这个有些YouTube视频我看了）
However I believe that I have a compelling argument that my algorithm runs in O(n) space. I know that space complexity is "the total space taken by an algorithm with respect to the input size" Space Complexity and is relative to the the depth of a recursive call(remember this from some Youtube video I watched)
一个例子，我有正在产生[1,2,3]作为[1,2,3]的一个子集。下面是一组递归调用生成一套
generateSubsets（[]，子集，[1,2,3]）
generateSubsets（[3]，子集，[1,2]）
generateSubsets（[2,3]，子集，[1]）
generateSubsets（[1,2,3]，子集，[]）
An example I have is generating [1,2,3] as a subset of [1,2,3]. Here is the set of recursive calls to generate that set
generateSubsets([], subsets, [1,2,3])
generateSubsets([3],subsets,[1,2])
generateSubsets([2,3],subsets,[1])
generateSubsets([1,2,3],subsets,[])
这表明，相对于原设定大小为n的递归调用的最大深度为n本身。所有这些递归调用都会有自己的堆栈帧。所以从这个，我的结论是，空间复杂度的 O（N）的没有人看到任何在我的证据瑕疵？
This show that the greatest depth of a recursive call with respect to the original set size n is n itself. Each of these recursive calls will have its own stack frame. So from this, I concluded that the space complexity is O(n) Does anyone see any flaws in my proof?
推荐答案
您需要考虑到这是由你的算法（或者，分配的所有内存，而，分配的内存也就是使用，在任何的最大金额时间） - 不仅在栈上，而且在堆上。每个生成的子集被存储在子集名单，这最终将包含2 的 N 的套，每大小介于0和 N 的（与大多数套含周围的 N 的/ 2个元素） - 这样的空间复杂度实际的 0 的（<我> N 2 的 N 的）。
You need to take into account all memory that is allocated by your algorithm (or, rather, the greatest amount of allocated memory that is "in use" at any time) - not only on the stack, but also on the heap. Each of the generated subsets is being stored in the subsets list, which will eventually contain 2n sets, each of size somewhere between 0 and n (with most of the sets containing around n / 2 elements) - so the space complexity is actually O(n 2n).
这篇关于这是集算法实际上是O（n）的空间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
