关于面试时快排空间复杂度的讨论

面试时说了下快排,问了空间复杂度,我说最好情况下log2 n,最差为n,面试官然后说,网上有些说空间复杂度是n*log2 n,问我哪个是对的,我坚持说我的是对的,回来网上查了一下,还真有一些博客说是n*log2 n,后背一阵凉啊,各位怎么看
全部评论
nlog2n是时间复杂度 log2n是空间复杂度 ps:我是看考研书上写的
点赞 回复 分享
发布于 2016-09-26 18:27
空间复杂度 O(n) 吧,额外空间是 O(1)。 时间复杂度的期望是 O(nlogn) , worst case 是 O(n^2) 不能再低了,就算是 random pivot 最坏复杂度也是平方级。
点赞 回复 分享
发布于 2016-09-26 22:20
空间复杂度 log2n 是怎么做到的?
点赞 回复 分享
发布于 2016-09-26 22:16
快排最好不是nlogn最坏是n^2么?
点赞 回复 分享
发布于 2016-09-26 20:33
平均是logn最坏是n。这个应该是和快排递归的深度有关系
点赞 回复 分享
发布于 2016-09-26 18:29
你的是对的
点赞 回复 分享
发布于 2016-09-26 18:20
网上是错的
点赞 回复 分享
发布于 2016-09-26 18:17

相关推荐

10-28 10:48
已编辑
门头沟学院 Java
孩子我想要offer:发笔试后还没笔试把我挂了,然后邮箱一直让我测评没测,后面不知道干嘛又给我捞起来下轮笔试,做完测评笔试又挂了😅
点赞 评论 收藏
分享
09-21 21:14
门头沟学院
否极泰来来来来:和他说:这里不好骂你,我们加个微信聊
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务