10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1178|回复: 5
收起左侧

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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了……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-21 06:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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