美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 帅爆!宝马X2量产版曝光:颜值无敌
  • 手动挡急刹车要不要踩离合?实测对比震惊
  • 最后一辆法拉利旗舰卖出:本世纪最贵的汽车!
  • 汽车购置税优惠要缩水:要买趁早
  • 喜欢大力关车门?看看这些...
  • 2017年北京市将实施“世界最严”锅炉排放标准
  • 国产“守望先锋”上线差评如潮:丢人丢到Steam
  • 收13万聘礼后失踪 游戏里的新娘竟是男保安
  • LOL女主播夏美酱一大波新照福利满满:发育得更好了
  • 《古墓丽影》手游移植PC:回合制游戏竟要求GTX 970!
  • 美国9月房价指数反弹,并升至历史纪录新高-美国房产信息
  • 有分析认为到美国留学的学生数目持续上升的趋势有可能在特朗普上台後终止-美国留学指 ...
  • 10个你永远不会有100万美元的原因
  • 2016年销售额近5000亿美元,2017年全球广告支出将放缓
  • 我在印度花了98分钟在ATM队列
  • 石油巨头正处于麻烦之中
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3007|回复: 10

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

[复制链接]
TA在交友中心
0 0 18
  @ME:   

7

主题

30

帖子

48

积分

新手上路

Rank: 1

积分
48
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?

新浪微博官方账号】美国华人网FunInUSA : 每日滚动更新美国商业投资就业招聘留学移民资讯。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 45
  @ME:   

20

主题

90

帖子

132

积分

注册会员

Rank: 2

积分
132
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?
TA在交友中心
0 0 65
  @ME:   

32

主题

95

帖子

160

积分

注册会员

Rank: 2

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


n^2

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



--

TA在交友中心
0 0 10
  @ME:   

6

主题

229

帖子

239

积分

中级会员

Rank: 3Rank: 3

积分
239
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
--
TA在交友中心
0 0 45
  @ME:   

20

主题

80

帖子

121

积分

注册会员

Rank: 2

积分
121
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可以避免吗?



--
TA在交友中心
0 0 54
  @ME:   

24

主题

91

帖子

139

积分

注册会员

Rank: 2

积分
139
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?

TA在交友中心
0 0 31
  @ME:   

15

主题

102

帖子

130

积分

注册会员

Rank: 2

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


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

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



--
TA在交友中心
0 0 55
  @ME:   

26

主题

95

帖子

143

积分

注册会员

Rank: 2

积分
143
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啊,很耽误时间的。



--
TA在交友中心
0 0 44
  @ME:   

19

主题

83

帖子

124

积分

注册会员

Rank: 2

积分
124
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?
TA在交友中心
0 0 53
  @ME:   

26

主题

101

帖子

146

积分

注册会员

Rank: 2

积分
146
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的复杂度吧- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

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

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

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

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