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

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

相关推荐

昨天 16:26
TP-LINK_软件算法工程师(准入职员工)
TP-Link内推，TP-Link内推码
🎈下面是面试过程 0.自我介绍+项目介绍 1.咱们家是哪里的 2.本科成绩怎么样 3.考研多少分（保研的） 4.是学硕对吧？奖学金拿过多少次？ 5.发过论文、专著之类的吗？（无） 6.有没有参加过什么比赛拿到省级以上奖励？ 7.有实习经历吗？ 8.创建线程都有哪些方式？ 9.JVM分为哪些区域？ 10.MySQL除了增删改查之外，还知道哪些关键字？ 11.having子句有什么作用？ 12.redis有哪些数据结构？ 13.用过消息中间件吗？知道哪些？ 14.这些消息队列使用场景有什么区别吗？ 15.设计模式知道哪些？ 16.你在学校最有成就感的一件事情是什么？ 17.现在有其他公司offe...
点赞 评论 收藏
分享
02-24 19:00
九州通医药集团_集团业务管培生(准入职员工)
步步高内推，步步高内推码
步步高实验学校 2026届校招启动啦【学校简介】东莞市步步高实验学校于 2023 年投入运营，占地 230 亩，是一所集幼儿园、小学、初中、高中于一体的十五年一贯制非营利性高端民办学校，学校全面实行小班化教学，学校师生比为 1:5；步步高教育专家团队由来自一流大学的国家课标专家、教育学家，来自著名学校的卓越校长，来自一线、有着丰富教学经验的著名特级教师，以及来自国家级教育媒体的教育策划专家共同组成，为步步高的课程、教学、管理奠定了坚实基础。【招聘岗位】• 幼儿园、小学部及初中部各学科类教师 & 国际教师，类别多多，等你pick！ 【福利待遇】• 薪资：幼儿园老师年收入16万起 、中小学...
点赞 评论 收藏
分享
2025-12-29 23:01
江西财经大学 外贸业务员
求一个不把应届生当cs的城市
我真有点想骂人了
脑袋锈住了：你这算啥，哥们中科院中强所硕士，本科211，叫我去干分拣，时薪20
点赞 评论 收藏
分享
02-12 10:58
南阳师范学院 Web前端
点赞 评论 收藏
分享
昨天 15:37
科大讯飞_语言算法工程师(准入职员工)
禾赛科技内推，禾赛科技内推码
禾赛科技软件测试面经全程一个小时左右，需要写SQL和代码- 自我介绍- 项目提问- 项目里面的好友列表咋做数据库设计的- TCP四次挥手- python基本数据结构- 列表和数组的区别- 写SQL（用到分组、排序、聚合函数）- 写代码（输入一个数，各个位上两两交换位置，输出最大的数）全球激光雷达Top禾赛科技26届校招【企业介绍】全球领先的激光雷达研发与制造企业，全球激光雷达市占率No.1，美国纳斯达克上市。【开放岗位】商务类、产品类、项目管理类、销售类、系统类、芯片类、光学类、机械类、电子类、软件类、算法类、测试类、制造类【面向人群】毕业时间：2024.7-2025.12【工作地点】上海、杭...
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 开工第一帖 #
12172次浏览 261人参与
# 携程求职进展汇总 #
882141次浏览 5791人参与
# xx岗简历求拷打 #
3995次浏览 48人参与
# 工作不开心辞职是唯一出路吗 #
7916次浏览 30人参与
# 有转正机会的小厂实习值得去吗？ #
5852次浏览 72人参与
# 掌握什么AI技能，会为你的求职大大加分 #
4220次浏览 192人参与
# 实习期间如何提升留用概率？ #
241430次浏览 1824人参与
# 为什么国企只招应届生 #
238705次浏览 1300人参与
# 参加完秋招的机械人，还参加春招吗？ #
111083次浏览 709人参与
# 哪些公司开春招了？ #
32614次浏览 204人参与
# 秋招你经历过哪些无语的事 #
101322次浏览 597人参与
# 金三银四，你有感觉到吗 #
691414次浏览 6088人参与
# 毕业季等于分手季吗 #
54876次浏览 654人参与
# 牛客租房专区 #
160105次浏览 1915人参与
# 联想求职进展汇总 #
334999次浏览 2220人参与
# 牛友投递互助，不漏校招机会 #
439049次浏览 5243人参与
# 正在春招的你，也参与了去年秋招吗？ #
353058次浏览 2597人参与
# 你最讨厌面试被问什么 #
6106次浏览 80人参与
# 非技术er求职现状 #
139131次浏览 821人参与
# 你觉得今年春招回暖了吗 #
931164次浏览 7233人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务