关于面试时快排空间复杂度的讨论
面试时说了下快排，问了空间复杂度，我说最好情况下log2 n，最差为n，面试官然后说，网上有些说空间复杂度是n*log2
n，问我哪个是对的，我坚持说我的是对的，回来网上查了一下，还真有一些博客说是n*log2 n，后背一阵凉啊，各位怎么看
2016-09-26 18:06 石牌村文科职业技术学院 Java
关注
全部评论
克里斯汀娜
南昌大学 前端工程师
nlog2n是时间复杂度
log2n是空间复杂度
ps:我是看考研书上写的
heda
清华大学 算法工程师
空间复杂度 O(n) 吧，额外空间是 O(1)。 时间复杂度的期望是 O(nlogn) ， worst case 是 O(n^2)
不能再低了，就算是 random pivot 最坏复杂度也是平方级。
heda
清华大学 算法工程师
空间复杂度 log2n 是怎么做到的？
加班的卡夫卡
阿里巴巴_l_开发工程师
快排最好不是nlogn最坏是n^2么？
onionlo
上海交通大学 Java
平均是logn最坏是n。这个应该是和快排递归的深度有关系
这个人没有名字
杭州电子科技大学 Java
你的是对的
LeeKai.me
华中科技大学 Java
网上是错的
相关推荐
投递哔哩哔哩等公司10个岗位 09-04 10:16
长春理工大学 Java 点赞 评论 收藏
分享