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

面试时说了下快排,问了空间复杂度,我说最好情况下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

相关推荐

身边有人上海、深圳 6、7k 都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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