一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 315|回复: 4
收起左侧

[学Java/C#] 话说,merge sort的空间复杂度可以优化成 lg n 吗?

[复制链接] |试试Instant~ |刷题, 学java/c#
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (215)
 
 
26% (78)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
如题,假如每一层,我是in place的merge呢?

call stack每一个栈帧一定要O(n)而不是O(1)吗?

一共是lg n层

上一篇:出一个leetcode会员 2020年9月到期
下一篇:leetcode contest题目质量下降的厉害
我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (576)
 
 
1% (6)    👎
不可能,如果有log n的sort下一个图灵奖就是你的。我没有看懂为什么in place sort就能省掉一个n

补充内容 (2020-4-5 09:10):
哦哦,老夫眼瞎了,空间复杂度,不好意思楼主

补充内容 (2020-4-5 09:16):
但是in place merge sort会影响到时间复杂度,可能时间复杂度不再是nlogn
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (576)
 
 
1% (6)    👎
602689817 发表于 2020/04/06 00:08:31
不可能,如果有log n的sort下一个图灵奖就是你的。我没有看懂为什么in place sort就能省掉一个n
哦哦,老夫眼瞎了,空间复杂度。不好意思楼主
回复

使用道具 举报

我的人缘0
 楼主| zebointexas 2020-4-6 00:55:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (215)
 
 
26% (78)    👎
602689817 发表于 2020-4-6 00:10
哦哦,老夫眼瞎了,空间复杂度。不好意思楼主

哦哦没事 啊
回复

使用道具 举报

我的人缘0
usr_opta 2020-4-6 07:09:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
线性时间的原地merge似乎是存在的:http://akira.ruc.dk/~keld/teachi ... kler/04/Huang88.pdf
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-6-2 07:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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