美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 全球首个“机械战警”上岗:高1米7/重200斤
  • 无意识行为透露个性特征:早餐也吃辣或性格开朗
  • 2017年应届毕业生就业调查:平均月薪4014元
  • 爱因斯坦这个理论争议了100年:科学家尝试证明
  • 不愧“四害之首” 精子连宇宙射线都杀不死
  • NASA预警:即将有五颗小行星擦过地球
  • 无辐射!超级激光新用途:实时监测生物体内状况
  • 太空冷冻老鼠精子产出小鼠:太空繁育或成真
  • 两个AlphaGo对战谁会赢?答案很简单
  • NVIDIA市值达800亿美元 日本软银成第四大股东
  • 被美国收养的子女不能为亲属办绿卡
  • 6个月高位:强劲数据、强硬言论助力欧元
  • 美元大跌——成也特朗普,败也特朗普
  • 小瞧高通! 你可就错了
  • 黄金十字:逆势扭转,贵金属是要翻身了啊!
  • 焦点:特朗普"2018预算案"周二首秀
  • 警告:小心债券市场带来寒意
  • 诺贝尔物理学奖得主:我身上百分百流的是中国人的血液
  • 周二关键词:美联储与中国市场
  • 加州大洛杉矶分校少年班亚裔超四成
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3032|回复: 10

内推面经 -说说4sum的复杂度吧- 唐人社区|北美华人论坛

[复制链接]

8

主题

33

帖子

53

积分

新手上路

Rank: 1

积分
53
QQ
发表于 2016-11-6 18:06:09 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-说说4sum的复杂度吧


  JobHunting
标 题: 说说4sum的复杂度吧


LC 4Sum O(n^3)是time complexity下届吗?我怎么觉得不是呢?
--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

21

主题

96

帖子

141

积分

注册会员

Rank: 2

积分
141
QQ
发表于 2016-11-6 19:58:14 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


看看这个帖子,他的证明好像没问题啊。O(n^3)是下届
https://discuss.leetcode.com/topic/27445/lower-bound-n-3/14

我现在突然之间全糊涂了。Big O是upper bound of all cases啊,我一直以为是
average case呢。

那么我们为什么说quick sort是 O(nlogn)? 如果是worst case不是O(n^2)吗?是因为
优化partition可以避免吗?

【 在 flamingos (flamingos) 的大作中提到: 】
: 当然不是 http://www.sigmainfy.com/blog/4sum-problem-analysis-different-time-complexity.html


--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

37

主题

109

帖子

183

积分

注册会员

Rank: 2

积分
183
QQ
发表于 2016-11-6 20:00:01 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


n^2

【 在 coldknight (冷骑士) 的大作中提到: 】
: LC 4Sum O(n^3)是time complexity下届吗?我怎么觉得不是呢?



--

7

主题

241

帖子

243

积分

中级会员

Rank: 3Rank: 3

积分
243
QQ
发表于 2016-11-6 20:34:57 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


当然不是 http://www.sigmainfy.com/blog/4sum-problem-analysis-different-time-complexity.html

--
☆ 发自 iPhone 买买提 1.23.01
--

23

主题

87

帖子

138

积分

注册会员

Rank: 2

积分
138
QQ
发表于 2016-11-6 20:36:38 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


quick sort 一直是n^2。只是一般情况下run的比nlgn的都快而已

【 在 coldknight (冷骑士) 的大作中提到: 】
: 看看这个帖子,他的证明好像没问题啊。O(n^3)是下届
: https://discuss.leetcode.com/topic/27445/lower-bound-n-3/14
: 我现在突然之间全糊涂了。Big O是upper bound of all cases啊,我一直以为是
: average case呢。
: 那么我们为什么说quick sort是 O(nlogn)? 如果是worst case不是O(n^2)吗?是因为
: 优化partition可以避免吗?



--

25

主题

95

帖子

151

积分

注册会员

Rank: 2

积分
151
QQ
发表于 2016-11-6 20:42:33 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


应该是 O(n^2 * m)吧  m is average duplicate 2sum number

1,2,3,4,5,6  
target 14

要找出所有解,肯定要处理2sum的duplicate

【 在 echoisles (echoisles) 的大作中提到: 】
: n^2




--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

21

主题

111

帖子

153

积分

注册会员

Rank: 2

积分
153
QQ
发表于 2016-11-6 21:16:09 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


尽量用theta,theta是average复杂度。

【 在 coldknight (冷骑士) 的大作中提到: 】
: 人生观颠覆了,面试的时候,一旦有sort,我都是告诉是O(nlogn) 复杂度,面试官从
: 没异议。 难道以后面试当问到复杂度的时候,每次都要说清楚average, worst case
: 和 best case啊,很耽误时间的。



--

31

主题

108

帖子

183

积分

注册会员

Rank: 2

积分
183
QQ
发表于 2016-11-6 21:17:45 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


一般说average的O问题应该不大
但是如果能同时说出worst的O,应该可以加分
如果面试官想问worst O,可能会follow up问。。

【 在 coldknight (冷骑士) 的大作中提到: 】
: 人生观颠覆了,面试的时候,一旦有sort,我都是告诉是O(nlogn) 复杂度,面试官从
: 没异议。 难道以后面试当问到复杂度的时候,每次都要说清楚average, worst case
: 和 best case啊,很耽误时间的。



--

22

主题

90

帖子

138

积分

注册会员

Rank: 2

积分
138
QQ
发表于 2016-11-6 21:48:15 | 显示全部楼层
JobHunting
标  题: 说说4sum的复杂度吧


LC 4Sum O(n^3)是time complexity下届吗?我怎么觉得不是呢?
--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

32

主题

117

帖子

181

积分

注册会员

Rank: 2

积分
181
QQ
发表于 2016-11-6 21:56:49 | 显示全部楼层
JobHunting
标  题: Re: 说说4sum的复杂度吧


人生观颠覆了,面试的时候,一旦有sort,我都是告诉是O(nlogn) 复杂度,面试官从
没异议。 难道以后面试当问到复杂度的时候,每次都要说清楚average, worst case
和 best case啊,很耽误时间的。

【 在 integer (integer) 的大作中提到: 】
: quick sort 一直是n^2。只是一般情况下run的比nlgn的都快而已



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -说说4sum的复杂度吧- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -说说4sum的复杂度吧- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

安全联盟认证 安全联盟认证

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