Combinations和Subset时间复杂度比较[Leetcode]

Leetcode上两道题目, Combinations和Subsets, 时间复杂度分别是多少?
我觉得Combinations的递归方法复杂度是O(n!)而Subsets的复杂度也是O(n!）
理由: Combinations的递归方法每次递归要检查n个元素(或者n-1个，n-2个..),总共要做n!次
而Subsets其实就是做2^n次Combinations来获取Subsets, 因此复杂度是O(2^n * n!) = O(n!)

但是根据在这里看到的解: https://github.com/soulmachine/leetcode
Combinations的时间复杂度是O(n!)而Subsets的时间复杂度是O(2^n)，
可是O(n!)>O(2^n)，一个子问题(Combinations)的时间复杂度是不可能大于主问题的(Subsets)

另外还有一种意见：https://oj.leetcode.com/discuss/24964/o-2-n-or-o-n?show=25008#a25008
这里的stellari说Combinations的时间复杂度不是O(n!),而是远远小于O(2^n)<O(n!)

有什么建议吗?

那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对没说过Combination的时间复杂度“远小于”O(2^n)，我说的是O(Combination) 小于等于 O(2^n).

首先，我想你之所以会认为combination是O(n!)，可能主要来自你在leetcode上贴的这段代码：

1.         
   
2. for (int i=begin;i<=end;i++){
   
3.             comb.push_back(i);
   
4.             recursion(i+1,end,comb,result,k-1);
   
5.             comb.pop_back();
   
6.         }
   

复制代码

看起来，在f(n)中是总共做了n次循环，每次又调用了f(n-1)，所以有
T(n) = nT(n-1) + kn + c;
如果按这个公式来的话，确实是O(n!)没错。

但是事实上，注意循环中的第二句
recursion(i+1,end,comb,result,k-1);
中的第一个参数是i+1, 而不是i。也就是说，这f(n)中的n次递归调用并不都是f(n-1)，而是f(n-1), f(n-2), f(n-3), ... f(1), f(0). 你可能直觉上觉得这两者差不多，比如n + n + n + ... + n (n 个 n) 是 O(n^2) 级别的，而 1 + 2 + 3 + .. + n 也是O(n^2)级别的。但是这里不同，这里是递归调用。第一层递归中省下来的哪怕一次循环在后续的递归调用中都会被以至少指数等级放大。所以，就是这一点i和i+1的差别，导致了O(n!)和O(2^n)的区别。

你说的github上的解我没有看。如果作者说Combination是O(n!)的，那么有可能他也是犯了上面的失误。

Subset是做了n次时间复杂度不同的Combination（不是2^n次）。因为k总共只能有n种取值。将k取一个值，做一次Combination，最后n次做完就得到Subset的解。

另外多说一句，你谈到O(2^n * n!) = O(n!)，这个关系其实是不成立的。因为你并不能找到一个常数K，使得K * n! 对于任何n来说都大于 2^n * n! 。但是O(2^n + n!) = O(n!)则可以，因为你能够找到一个常数K（任何大于等于3的数字都可以），使得Kn! > 2^n + n!

如果真的要细扣的话，Subset总共产生2^n个Subset，但是每个Subset的长度是n数量级的，所以Subset的复杂度应该是O(n*2^n) （你可以自行验证一下，所有subset中的元素个数总数是n*2^(n-1)）。这个式子严格来说不能写成O(2^n)。不过为了突出这个式子中的最大头部分2^n，很多人 ( 比如我 ) 还是简单地说这个算法是“指数运行时间”的，并把n略去不写，只是咱们自己还是要清楚那里其实有个n在那里。同理，Combination的复杂度其实也是O(k * C(n, k))。

赞楼上！
刚好在某本书上碰到这两道题，subset这道题的答案的解释是：

The number of recursive calls, T(n) satisfies the recurrence T(n) = T(n - 1) + T(n - 2) + ... + T(1) + T(0), which solves to T(n) = O(2^n). Since we spend O(n) time within a call, the time complexity is O(n2^n);

houhahha 发表于 2017-12-10 04:04
有个疑问：subset时间复杂度就是2^n吧，结果2^n个，每次操作是1（因为是基于上一步的结果，只加了一个元素 ...

要考虑把每一个subset的list拷贝到result的时间的话 还要再乘以一个n，就是subset里list的长度

Combinations 的时间复杂度为什么是 O(n!) 呢?

我觉得应该是:
O(n)=O(n-1)+O(n-2)+...+O(1)

另一个角度看是 O(C(n, k)) 肯定比 O(2^n) 小

stellari 发表于 2015-2-27 23:32
那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对 ...

谢谢啊，我后来理解了，recursion的时间不是线性增加或减少的，所以计算起来不能一概而论。
之前问的问题也是由于我对O(n)计算理解不够清楚

monkerek 发表于 2015-3-1 09:52
赞楼上！
刚好在某本书上碰到这两道题，subset这道题的答案的解释是：

Good Reference, thanks

stellari 发表于 2015-2-27 23:32
那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对 ...

你好，想请问几个问题，感谢！
1. 关于Subsets的时间复杂度，我这么分析理解可以吗？
相当于最后的解集是不同的解组合，因此一共n个数字的话，我们的解集有2^n个。然后 对于递归解空间为树状结构的复杂度分析，我们就分析一共探索了多少个节点，由Subsets问题中的解空间结构，我们知道每个节点就是一组解，有2^n个解即2^n个节点。因此复杂度是O(2^n)。其中，回溯的时候虽然又访问了之前访问过的节点但是可以看做此时回来后立马去探索出了下一个活节点，因此总体上看来近似就是探索了这么多个节点。

2. 另外就是空间复杂度，面试的时候如果问这个题的空间复杂度，是不是我只需要说递归时消耗的系统栈的空间O(n), 不用管最后得到的解集所占用的空间是吗？

3. 另外就是permutations这个题的时间复杂度该咋分析呢？也能根据解集个数来n!来分析吗？但是这样的话又跟之前1中的，访问的节点数似乎又矛盾了。

问题有点儿多，求指教，感谢啊！

水逼一枚 发表于 2015-6-27 02:36
你好，想请问几个问题，感谢！
1. 关于Subsets的时间复杂度，我这么分析理解可以吗？
相当于最后的解集 ...

1. 可以是可以，不过我个人觉得这种分析只是用数学方法推出“解集”的个数2^N，并获得得到解集的平均时间O(N)，最终得到时间复杂度O(N*2^N)，其实并没有真正去分析“解空间树”。解空间树在我的理解中并非“每个节点是一个解”，而是“每个叶节点是一个解”。这个树有2^N个叶节点，但是如果算上所有中间的节点的话，总时间复杂度是O(N*2^N)。

2. 我觉得你最好把栈空间和解集所消耗的内存都说出来，并且明确说出“所用的栈空间远低于解集所用的空间”。
3. permutations是这个样子的，比如我写的这段代码：

1.     vector<vector<int> > res;
   
2.     vector<int> sol;
   
3.     void DFS(vector<int>& nums, int id) {
   
4.         if (id == nums.size()) {res.push_back(sol); return;}
   
5.         
   
6.         for (int i = id; i < nums.size(); ++i) {
   
7.             swap(nums[id], nums[i]);
   
8.             sol[id] = nums[id];
   
9.             DFS(nums, id+1);
   
10.             swap(nums[id], nums[i]);
    
11.         }
    
12.     }
    
13. public:
    
14.     vector<vector<int>> permute(vector<int>& nums) {
    
15.         sol = vector<int> (nums.size(), 0);
    
16.         DFS(nums, 0);
    
17.         return res;
    
18.     }

复制代码

每次函数F(N)中递归调用了N次函数F(N-1)，所以总共有 T(N) =NT(N-1) = N*(N-1) * T(N-2)...T(1)T(0)= N! * T(0) 这么多次函数调用。又因为当每次输入的元素个数N=0时，需要将一个解压入解集。这是一个O(N)操作，也就是T(0) = N, 所以复杂度是O(N!*N)。

你用解集数来估计得到的结果也是一样的：N个数的全排列是N!种，故共有N!个解，每个解需要O(N)时间构造，所以总时间是O(N!*N)

这和1中的节点分析不矛盾。Permutations的解空间树是一棵"complete"的树（对于第K层的任意节点，一定有N-k个children），而Subsets的解空间树则非常稀疏。

stellari 发表于 2015-2-27 23:32
那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对 ...

我擦，你就是这个啊，难怪感觉在哪里看过你的名字，原来在leetcode上

请问，怎样你是如何给leetcode出题的啊，题目从哪来，你的test case如何产生，用什么方法，谢啦



Activity by stellari

Score:        27,070 points (ranked #4)
Questions:        12
Answers:        174 (44 chosen as best)
Comments:        47
Voted on:        22 questions, 3 answers
Gave out:        11 up votes, 14 down votes
Received:        557 up votes, 8 down votes

monkerek 发表于 2015-3-1 09:52
赞楼上！
刚好在某本书上碰到这两道题，subset这道题的答案的解释是：

请问是哪本书呀～！可以说一下吗