一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4675|回复: 16
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
mattsun 发表于 2015-2-16 07:52:06 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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!)

有什么建议吗?

本帖被以下淘专辑推荐:

stellari 发表于 2015-2-27 23:32:19 | 显示全部楼层
那个,先自我介绍一下,我就是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))。


评分

2

查看全部评分

回复 支持 6 反对 0

使用道具 举报

stellari 发表于 2015-10-19 21:29:31 | 显示全部楼层
duffywan 发表于 2015-10-18 00:27
谢stellari回答,对于recursion / backtracking 一类的题一直分析部清楚run time.
请教另外一题:
http ...

你说的应该是对的,多谢指出。我其实是先写完S-G的算法然后再返回头来写的开头的那一段,可能是把两者混起来了。我分析的那个时间复杂度其实是:“在使用S-G函数,但是不使用DP计算函数值”的情况下的时间复杂度。

至于那个式子怎么reduce到2^(N)的,如果T(N) = 2 * sum(T(1)...T(N-2)) ,那么T(N-1) = 2 * sum(T(1)..T(N-3))。所以T(N) = T(N-1) + 2*T(N-2)。

很明显,如果T(N) = 2^N的话,那么T(N-1) = 2^(N-1), 2*T(N-2) = 2^(N-1)。后两者的和恰好是2^N。所以T(N)的表达式就是2^N。这可能听起来有点置因为果的感觉,但是一般只要能找到一个满足递推公式的通项公式,那么这个通项公式就是T(N)的表达式。在咱们遇到的题的范围内应该不会有例外。
回复 支持 1 反对 0

使用道具 举报

hekkd 发表于 2015-2-17 16:03:10 | 显示全部楼层
Combinations 的时间复杂度为什么是 O(n!) 呢?

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

另一个角度看是 O(C(n, k)) 肯定比 O(2^n) 小
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-3-1 09:52:22 | 显示全部楼层
赞楼上!
刚好在某本书上碰到这两道题,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);
回复 支持 反对

使用道具 举报

 楼主| mattsun 发表于 2015-3-3 07:11:39 | 显示全部楼层
stellari 发表于 2015-2-27 23:32
那个,先自我介绍一下,我就是Leetcode上的stellari,咱还是中文聊来得方便点吧。

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

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

使用道具 举报

 楼主| mattsun 发表于 2015-3-3 07:12:13 | 显示全部楼层
monkerek 发表于 2015-3-1 09:52
赞楼上!
刚好在某本书上碰到这两道题,subset这道题的答案的解释是:

Good Reference, thanks
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-6-27 02:36:48 | 显示全部楼层
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中的,访问的节点数似乎又矛盾了。

问题有点儿多,求指教,感谢啊!
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-27 10:01:13 | 显示全部楼层
水逼一枚 发表于 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的解空间树则非常稀疏。
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-27 18:35:30 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

duffywan 发表于 2015-10-17 10:14:51 | 显示全部楼层
monkerek 发表于 2015-3-1 09:52
赞楼上!
刚好在某本书上碰到这两道题,subset这道题的答案的解释是:

请问是哪本书呀~!可以说一下吗
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-10-17 10:46:28 | 显示全部楼层
duffywan 发表于 2015-10-17 10:14
请问是哪本书呀~!可以说一下吗

Elements of Programming Interviews
回复 支持 反对

使用道具 举报

duffywan 发表于 2015-10-18 00:27:39 | 显示全部楼层
stellari 发表于 2015-2-27 23:32
那个,先自我介绍一下,我就是Leetcode上的stellari,咱还是中文聊来得方便点吧。

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

谢stellari回答,对于recursion / backtracking 一类的题一直分析部清楚run time.
请教另外一题:
https://leetcode.com/discuss/643 ... ing-128ms-to-dp-0ms
这个帖子应该是你回的吧,想问下对于最基本的解法,也就是p1翻转一次往下递归,如果p2不能翻转了p1就赢了,你给的run time分析是:
T(N) = T(N-2) + T(N-3) + [T(2) + T(N-4)] + [T(3) + T(N-5)] + ...
        [T(N-5) + T(3)] + [T(N-4) + T(2)] + T(N-3) + T(N-2)
     = 2 * sum(T)  (i = 3..N-2)
You will find that T(N) = 2^(N-1) satisfies the above equation. Therefore, this algorithm is at least exponential.
有两个地方不懂:
1. T(n)这个式子怎么理解: 我自己分析的是
对于顶层:T(n) = (n - 1)T(n - 2),就是如果string全是”+“我们有n - 1个地方可以把它翻转成"--",最坏情况下对这每次翻转都要递归下去,因为已经翻转了两个,所以下一层需要处理的就是T(n-2)了。
把式子打开变成T(n) = (n - 1)(n-3)T(4) = (n - 1) (n - 3)(n-5).....1. 感觉和n!有点接近。
2. 如何reduce 到2^(N-1)

不好意思问得问题都很蠢,希望能被解答!
回复 支持 反对

使用道具 举报

duffywan 发表于 2015-10-28 23:42:27 | 显示全部楼层
monkerek 发表于 2015-10-17 10:46
Elements of Programming Interviews

谢谢!我最近也在看那个书,有一些variant的题目自己的思路不是很清楚 可以一起讨论下么
回复 支持 反对

使用道具 举报

monkerek 发表于 2015-10-29 01:26:13 | 显示全部楼层
duffywan 发表于 2015-10-28 23:42
谢谢!我最近也在看那个书,有一些variant的题目自己的思路不是很清楚 可以一起讨论下么

可以可以~
回复 支持 反对

使用道具 举报

duffywan 发表于 2015-10-29 05:31:58 | 显示全部楼层

给个邮箱或者联系方式呗~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 16:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表