一亩三分地论坛

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

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

[算法题] Combination Sum时间复杂度

[复制链接] |试试Instant~ |关注本帖
mattsun 发表于 2015-3-14 09:32:11 | 显示全部楼层 |阅读模式

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

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

x
在网上看到很多post说Leetcode的Combination Sum的时间复杂度是O(n!),这个n!是怎么来的?
我觉得时间复杂度应该是O(n*2^n),有点类似于subset
stellari 发表于 2015-3-14 20:53:49 | 显示全部楼层
哥们,别再纠结这个问题了。得到O(n!)答案的应该主要是下面两种情况:

1. 懂点算法分析基础,但是看到f(n)中有n次循环,就简单认为是O(n!)了,没有真的去分析。
2. 不懂算法分析,看到网上其他帖子中有说O(n!),就抄到自己的博客或刷题笔记上了。

网上的刷题笔记水平参差不齐,而且很多人其实都只是对时间复杂度有点初步概念,并不是真正地会从数学角度去分析。如果你实在不放心,你不妨看看StackOverflow上的人是怎么说的。
回复 支持 反对

使用道具 举报

 楼主| mattsun 发表于 2015-3-15 01:16:15 | 显示全部楼层
stellari 发表于 2015-3-14 20:53
哥们,别再纠结这个问题了。得到O(n!)答案的应该主要是下面两种情况:

1. 懂点算法分析基础,但是看到f( ...

好嘞,最近要G家面试,有点慌
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-15 01:47:32 | 显示全部楼层
mattsun 发表于 2015-3-15 01:16
好嘞,最近要G家面试,有点慌

……作为一个从G家onsite失败归来的人,我祝你好运……顺带一提,千万不要觉得刷完OJ上的题就万事大吉了;一定要做好见到和OJ上的题没有半毛钱关系的题的准备啊。
回复 支持 反对

使用道具 举报

 楼主| mattsun 发表于 2015-3-15 02:29:46 | 显示全部楼层
stellari 发表于 2015-3-15 01:47
……作为一个从G家onsite失败归来的人,我祝你好运……顺带一提,千万不要觉得刷完OJ上的题就万 ...

其实上个礼拜已经onsite完了,礼拜一加面一轮
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-15 21:25:58 | 显示全部楼层
mattsun 发表于 2015-3-15 02:29
其实上个礼拜已经onsite完了,礼拜一加面一轮

onsite也有加面啊?好吧,我out了……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 03:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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